A constellation of n communication satellites orbits a planet along a single fixed ring, numbered 0 through n - 1 in order around the ring, so that satellite n - 1 sits immediately next to satellite 0. Each satellite is currently transmitting an integer broadcast code. Every minute, mission control issues one synchronized command to the entire ring: simultaneously, every satellite either keeps transmitting its own current code, or switches to transmit whichever code the satellite immediately clockwise from it was transmitting, or whichever code the satellite immediately counter-clockwise from it was transmitting — using the codes exactly as they stood the instant before that minute began. Mission control wants to reach a minute after which every satellite in the ring is transmitting the exact same code (it does not matter in advance which code that ends up being). Determine the minimum number of minutes mission control needs to guarantee this.

Input format

Line 1: a single integer n, the number of satellites. Line 2: n space-separated integers code_0, code_1, ..., code_{n-1}, the current broadcast code of each satellite in ring order.

Output format

Print a single integer: the minimum number of minutes needed until every satellite transmits the same code.

Constraints

• 1 <= n <= 100000
• 1 <= code_i <= 1000000000

4
1 2 1 2

1

5
2 1 3 3 2

2