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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад 1

Loading

Приклад 2

Loading

Приклад 3

Loading

Примітка

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

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

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

Оцінювання

( $9$ балів): усі елементи масиву $a$ рівні $1$ ;
( $15$ балів): $1 \leq a_{i} \leq 2$ 1 \le a_i \le 2 для $1 \leq i \leq n$ 1 \le i \le n; $a_{i} \leq a_{i + 1}$ a_i \le a_{i+1} для $1 \leq i < n$ 1 \le i < n;
( $14$ балів): $n \leq 8$ n \le 8;
( $17$ балів): $a_{1} = a_{n}$ a_1 = a_n;
( $12$ балів): $n \leq 2000$ n \le 2000;
( $12$ балів): $1 \leq a_{i} \leq 100$ 1 \le a_i \le 100 для $1 \leq i \leq n$ 1\le i\le n;
( $21$ бал): без додаткових обмежень.