After years of slaughter, the Qin Emperor finally unified China. To defend against foreign invasions, he prepared to station $n$ generals along the national border.

Unfortunately, these $n$ generals have grown powerful and begun to reveal their wolfish ambitions. They refuse to report for duty and refuse to accept the Emperor's imperial edicts. The Qin Emperor has already prepared to secretly execute these insolent border generals. However, to prevent a mutiny, he decided to first award these generals some medals to buy himself strategic time.

The generals were very happy to hear that they were about to be awarded medals and wrote to express their gratitude. The $i$-th general requests $a_i$ medals of different colors. However, these generals are very arrogant; if two adjacent generals possess medals of the same color, they will consider it a sign of disrespect from the Emperor and will immediately rebel (the general numbered $i$ and the general numbered $i+1$ are adjacent; since their stationed border can be viewed as a circle, the general numbered $1$ and the general numbered $n$ are also adjacent).

The Emperor has no choice but to satisfy each general's request, but he is very angry at their arrogance. Therefore, the Emperor decided to mint the minimum number of types of medals required to satisfy these arrogant individuals. What is the minimum number of colors of medals he needs to mint?

Input

The first line of the input contains an integer $n$ ($1 \le n \le 20000$). The next $n$ lines each contain an integer $a_i$, representing the number of medals the $i$-th general requests ($1 \le a_i \le 100000$).

Output

Output a single integer, which is the minimum number of medal colors required.

Examples

Input 1

4
2
2
1
1

Output 1

4