410611: GYM104065 G Let Them Eat Cake

Let them eat cake. King Bobo said while looking down at the $$$n$$$ poor people begging on their knees inside the majestic palace. What makes King Bobo different from Marie Antoinette is that King Bobo truly did offer them cakes.

King Bobo lets the $$$n$$$ people stand in a line, with the $$$i$$$-th $$$(1\leq i\leq n)$$$ people from the left having a label $$$a_i$$$. All labels are integers from $$$1$$$ to $$$n$$$ and pairwise distinct. King Bobo then offers the cakes in rounds, by the following rule:

• When only one person is in the line, King Bobo gives him/her a cake, and the process ends.
• Otherwise, King Bobo offers a cake to all people whose label is smaller than some of his/her adjacent people (Each person may have $$$1$$$ or $$$2$$$ adjacent people, for those with $$$2$$$ adjacent people, having a label smaller than either of the two can grant him/her a cake). Those who received the cake leave the line, and the remaining ones close the gaps and maintain the same order in the line. This counts as a round.

King Bobo wants to know how many rounds will be counted until the process ends. A king will never do the counting by himself, so it becomes your work.

The first line contains an integer $$$n$$$ $$$(1\leq n\leq 10^5)$$$, denoting the number of poor people.

The next line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq n,a_i\text{ is pairwise distinct} ) $$$, denoting the label of each person in the line from left to right.

Output an integer in a line, denoting the answer.

5
1 2 3 4 5

1

5
1 5 3 4 2

2

2
1 2

1

For the first sample test, in the first round, people with labels $$$1,2,3,4$$$ receive a cake and leaves the line, leaving the line with only one person. So the process ends in one round.

For the second sample test, in the first round, people with labels $$$1,2,3$$$ receive a cake and leaves the line; in the second round, the person with label $$$4$$$ receives a cake and leaves the line. So the process ends in two rounds.