Особа Т је добила низ \(A\) дужине \(N\). Једина дозвољена операција над низом је:

• Изабрати три произвољна различита индекса \((i, j, k)\), \(1 \leq i < j < k \leq N\) и поставити чланове низа \(A_i, A_j\) и \(A_k\) на средњи по вредности од та три елемента.

Наћи минималан број операција који особа Т мора направити тако да сви елементи низа \(A\) буду једнаки по вредности.

Опис улаза

• У првом реду улаза се налази позитиван цео број \(N\) - број елемената у низу \(A\).

• У другом реду улаза се налази \(N\) позитивних целих бројева, елементи низа \(A\).

Опис излаза

На излазу исписати минималан број операција потребан да низ \(A\) садржи све једнаке елементе по вредности.

Ограничења

• \(3 \leq N \leq 2\cdot10^5\)
• \(1 \leq A_i\leq 10^6\)

Тест примери су подељени у \(4\) дисјунктне групе:

• У тест примерима вредним \(10\) поена: Сви елементи низа \(A\) су различити.
• У тест примерима вредним \(10\) поена: У низу \(A\) се појављује највише две различите вредности.
• У тест примерима вредним \(20\) поена: \(N\leq 2000\).
• У тест примерима вредним \(60\) поена: Без додатних ограничења.

Примери

Пример 1

Улаз

5
1 2 3 2 5

Излаз

2

Објашњење

Особа Т прву операцију може применити над индексима \((2, 3, 4)\), низ се трансформише у \(A = [1, 2, 2, 2, 5]\). У другом операцији може изабрати индексе \((1, 2, 5)\) након чега сваки елемент низа \(A\) има вредност \(2\).

Пример 2

Улаз

3
1 1 1

Излаз

0