Description

After years of warfare, the First Emperor of Qin finally unified China. To defend against foreign invasions, he plans to station $n$ generals along the borders.

Unfortunately, these $n$ generals have grown powerful and begun to reveal their ambitions. They refuse to report for duty or accept imperial edicts. The emperor has prepared to secretly execute these insolent frontier commanders. However, to prevent a mutiny, he decides to first award them some medals to buy time.

The generals are delighted to hear they will be awarded medals and each sends a letter of thanks. The $i$-th general requests $a_i$ medals of different colors. However, the generals are proud: if two adjacent generals possess medals of the same color, they will consider it disrespectful and immediately rebel (generals numbered $i$ and $i+1$ are adjacent; because their border garrisons can be regarded as forming a circle, generals $1$ and $n$ are also adjacent).

The emperor must satisfy each general’s request, but he is furious at their arrogance. He decides to cast as few colors of medals as possible to meet their demands. What is the minimum number of medal colors he needs to cast?

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain an integer $a_i$, the number of different colors of medals requested by the $i$-th general.

Output Format

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

4
2
2
1
1

4

Hint

$1 \leq n \leq 2 \times 10^4$, $1 \leq a_i \leq 10^5$.

Translated by ChatGPT 5