Bajtazar's wife bought a beautiful necklace consisting of a certain number of pearls hung in sequence on a chain forming a circular loop. When the necklace is worn, all the pearls are at the front of the neck, and there is a piece of chain without pearls behind the head. However, the pearls are not permanently attached to the chain: any number of pearls from the ends can be slid along the chain around the head and placed at the other end of the necklace.

Bajtazar, as a great connoisseur of pearls, will certainly examine the pearls in the necklace one by one, analyzing them from left to right. Each pearl can be assigned a certain beauty level. As soon as Bajtazar sees a pearl more beautiful than all the previous ones, he will be delighted.

Bajtazar's wife likes it when Bajtazar is delighted, so she wants to arrange the pearls in the necklace (by moving some pearls from one end to the other) so that he is delighted as many times as possible. Calculate how many times this will happen.

Note that the pearls on the necklace are only pretty from the front side, so reversing the necklace (i.e., a left-right reflection) is not an option. It is also, of course, not possible to remove the pearls from the necklace and arrange them in a completely different order.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of pearls in the necklace. The second line contains a sequence of $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$); these are the beauty levels of the consecutive pearls in the necklace.

Output

Output the largest integer $k$ such that after moving a certain number of pearls from the beginning of the necklace to the end (without changing their relative order), there will be $k$ pearls in the necklace whose beauty level $a_i$ is strictly greater than the beauty levels of all pearls positioned before them.

Examples

Input 1

7
1 7 2 3 7 2 9

Output 1

4

Note

Explanation of the example: In the original arrangement of the necklace (drawing on the left), Bajtazar will be delighted three times: when seeing the first pearl, then when seeing the second pearl, and finally when seeing the last pearl; in particular, he will not be delighted when seeing the pearl with beauty level 7 again. However, if the first two pearls are moved to the end (drawing on the right), Bajtazar will be delighted four times: when seeing the pearls with beauty levels 2, 3, 7, and 9 for the first time.