Sinulle annetaan lista, jossa on $n$ lukua. Jokaisella siirrolla saat poistaa yhden luvun joko listan alusta tai lopusta. Mikä on pienin määrä siirtoja, joiden jälkeen listan ensimmäinen ja viimeinen luku on sama?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: lukujen määrä.

Seuraavalla rivillä on $n$ lukua $x_1,x_2,\ldots,x_n$: listan sisältö.

Tuloste

Tulosta yksi kokonaisluku: vastaus tehtävään.

Esimerkki

Syöte:

6
2 3 5 3 4 4

Tuloste:

3

Selitys: voit poistaa yhden luvun listan alusta ja kaksi lukua listan lopusta.

Osatehtävä 1 (25 pistettä)

• $1 \le n \le 100$
• $1 \le x_i \le 100$

Osatehtävä 2 (75 pistettä)

• $1 \le n \le 10^5$
• $1 \le x_i \le 10^9$