Competition of sequences#9631
Ziya will participate in the sequence competition tomorrow. A number x \ge 0 is called a peak of a sequence if the sequence
is a subsequence of the given sequence. The strength of a sequence is the largest of its peaks.
Tomorrow, all students will attend the competition, and the winner will be the owner of the strongest sequence. Ziya has a sequence a_1, a_2, a_3, \ldots, a_n. He wants to take over the scoring system and remove from consideration all sequences stronger than his own. However, Ziya does not know the strength of his sequence, but he really wants to win. Help him find the strength of his sequence.
The first line contains an integer (1 \le n \le 10^5) — the number of elements in Ziya's sequence. The second line contains integers a_i (1 \le a_i \le 10^5) — the elements of the sequence.
Print a single integer — the strength of the given sequence.
Example 1
Example 2
Example 3