T személy kapott egy \(N\) hosszúságú \(A\) sorozatot. Egyetlen engedélyezett művelet a sorozaton:

• Kiválasztani három tetszőleges \((i, j, k)\), \(1 \leq i < j < k \leq N\) indexet és az \(A_i, A_j\) és \(A_k\) elemek értékét beállítani e három elem (nagyság szerinti) középső elemének értékére.

Megtalálni a műveletek legkisebb számát, amelyet a T személynek el kell végezni ahhoz, hogy az A sorozat minden eleme azonos értékű legyen.

Bemenet

• A bemenet első sorában az \(N\) pozitív egész szám, az \(A\) sorozat elemeinek száma áll.
• A bemenet második sorában \(N\) pozitív egész szám áll. Ezek az \(A\) sorozat elemei.

Kimenet

A kimeneten kiíratni a a műveletek legkisebb számát, amely szükséges ahhoz, hogy az \(A\) sorozat minden eleme azonos értékű legyen.

Korlátozások

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

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: Az \(A\) sorozat minden eleme különböző.
• Tesztpéldák, melyek \(10\) pontot érnek: Az A sorozatban legfeljebb két különböző érték fordul elő.
• Tesztpéldák, melyek \(20\) pontot érnek: \(N\leq 2000\).
• Tesztpéldák, melyek \(60\) pontot érnek: nincs külön korlátozás.

Példák

1. példa

Bemenet

5
1 2 3 2 5

Kimenet

2

Magyarázat

A Т személy első műveletét a \((2, 3, 4)\) indexű elemeken hajtja végre, így a sorozat \(A = [1, 2, 2, 2, 5]\) lesz. A második műveletben az \((1, 2, 5)\) indexeket választja, ezután az \(A\) sorozat minden elemének értéke \(2\) lesz.

2. példa

Bemenet

3
1 1 1

Kimenet

0