403051: GYM100985 B MaratonIME plays Cîrokime

The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named "Cîrokime". The game works as follows:

First, n cups with Cîroc¹ are lined up. In front of the i-th cup a number a_i is written. It is guaranteed that a_i < a_i + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.

The player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup's number a_i is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.

"Cîrokime" is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home³

However, the DESMAME⁴ is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.

The first line has a single integer n, the number of cups. The second line has n integers a_i, the values hidden in each cup.

• 1 ≤ n ≤ 10⁵
• For all i, 1 ≤ a_i ≤ 10⁹
• For i < n, a_i < a_i + 1

The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.

3
2 5 7

2

8
1 2 3 4 5 6 7 8

4

1: Cîroc is a vodka brand made in France, known by its high sales price in market²

2: Balalaika also works

3: Based on real facts

4: Pre-BIFE⁵ party

5: University games that IME⁶ attends

6: Institute of Mathematics and Statistics