Plate Washing Sorting

Two cows, Bessie and Elsie, have devised a plate‐washing process. Initially, there is a stack of N dirty plates held by Bessie. The plates are labeled with a permutation of the integers from 1 to N (from top to bottom in the dirty stack). Elsie starts with an empty clean stack, and between them is a table used to hold soaped plates.

The process consists of a sequence of moves. In each move, one of the following operations is performed:

1. Bessie’s soaping move: She takes the top plate from the dirty stack, soaps it, and then places it on the table. When placing the soaped plate, she may either put it on top of an existing non‐empty pile on the table or start a new pile by placing it to the immediate right of all existing piles.

2. Elsie’s rinsing move: She takes the top plate from the leftmost pile on the table, rinses it, and places it on top of the clean stack.

At the end of the process the cows wish the clean stack to be sorted in increasing order when read from bottom to top (i.e. the smallest number is at the bottom and the largest at the top). However, given the rigid operation rules, it is not always possible to achieve this ordering.

Given the order of the dirty plates (as a permutation of 1 through N, with the first number representing the top plate) use the allowed moves in any interleaving order to determine the largest prefix (i.e. the first k plates) such that it is possible to eventually obtain a clean stack whose plate numbers are in increasing order from bottom to top.

It is guaranteed that at least one plate is always washable (that is, a prefix of length ≥ 1 is always feasible).

Note: When Elsie rinses a plate from a pile, she removes the top plate of that pile. The final clean order is obtained by the sequence in which plates are rinsed (first rinsed is at the bottom of the clean stack, last rinsed is on top).

All formulas are written in LaTeX. For example, the number of plates is given as $N$, and the plates are labeled with a permutation of $\{1,2,\ldots,N\}$.

inputFormat

The input begins with a single integer N ($1 \leq N \leq$ [small limit for simulation]) representing the total number of plates.

The next line contains N space‐separated integers representing a permutation of $\{1,2,\ldots,N\}$. The first integer is the plate at the top of the dirty stack.

outputFormat

Output a single integer—the maximum prefix length, k, such that the first k plates can be washed (via a sequence of allowed moves) so that the clean stack ends up sorted in increasing order (with the smallest number at the bottom and the largest at the top).

sample

5
2 1 5 3 4

2