eolymp
bolt
Try our new interface for solving problems
Problems

Competition of sequences

Competition of sequences

Ziya will take part in the sequence competition tomorrow. The number $x \ge 0$ is called the top of some sequence if the sequence $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ is a subsequence of this sequence. The strength of each sequence is considered to be its largest vertex. Tomorrow all students will go to the competition and the winner of the strongest sequence will be the winner. Zia has the sequence $a_1, a_2, a_3, ..., a_n$. He wants to take over the competition scoring system and remove sequences from it with more force than himself. However, Zia does not know the power of his own consistency, but really wants to win. Help him calculate the strength of his own sequence. \InputFile The first line contains the number $n~(1 \le n \le 10^5)$ of numbers in Zia's sequence. The next line contains $n$ integers $a_i~(1 \le a_i \le 10^5)$ --- the elements of the sequence. \OutputFile Print one number --- the strength of the given sequence.
Time limit 1 second
Memory limit 128 MiB
Input example #1
2
2 10
Output example #1
0
Input example #2
3
1 2 3
Output example #2
1
Input example #3
5
1 10 2 3 1
Output example #3
2
Source 2018 - 2019 Azerbaijan Republic Semifinals