Масив і додавання на відрізку

Задано масив цілих чисел $a$ довжини $n$.

Ви можете змінювати масив, використовуючи операцію додавання. Для того, щоб застосувати операцію додавання, необхідно виконати три послідовні дії:

1. вибрати довільне ціле число $x$;

2. вибрати довільний підвідрізок масиву $[l;r]$;

3. до кожного елементу вибраного підвідрізку додати $x$ (виконати операцію присвоєння $a_i\leftarrow (a_i+x)$ для $l\le i\le r$).

Знайдіть мінімальну кількість операцій додавання, необхідну для того, щоб усі елементи масиву $a$ стали попарно різними.

Вхідні дані

У першому рядку задано одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) — довжина масиву.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — елементи масиву.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій додавання, необхідну для того, щоб усі елементи масиву $a$ стали попарно різними.

Приклади

Примітка

У першому прикладі усі елементи масиву $a$ є попарно різними.

У другому прикладі після застосування двох операцій додавання з параметрами $x=-3$, $l=1$, $r=2$ та $x=-1$, $l=1$, $r=3$ масив $a$ стає рівним $[-2,-1,1,3,2]$.

У третьому прикладі після застосування двох операцій додавання з параметрами $x=-3$, $l=4$, $r=8$ та $x=-10$, $l=7$, $r=9$ масив $a$ стає рівним $[2,3,1,-2,0,-1,-12,-10,-7]$.

Оцінювання

1. ($9$ балів): усі елементи масиву $a$ рівні $1$;

2. ($15$ балів): $1\le a_i\le 2$ для $1\le i\le n$; $a_i\le a_{i+1}$ для $1\le i<n$;

3. ($14$ балів): $n\le 8$;

4. ($17$ балів): $a_1=a_n$;

5. ($12$ балів): $n\le 2000$;

6. ($12$ балів): $1\le a_i\le 100$ для $1\le i\le n$;

7. ($21$ бал): без додаткових обмежень.