P6099 [USACO19FEB] Dishwashing G

Bessie and Elsie are helping Farmer John wash dishes, which is a more complicated process than people might think.

The two cows decide that Bessie will apply soap, and Elsie will do the rinsing. At the beginning, $N$ dirty dishes (guaranteed to be a permutation of $1$ to $N$) are stacked on Bessie's side, while Elsie's stack is empty. Between them, there is a table specifically used to hold soaped dishes. Each rinsing step must perform one of the following two operations: - Bessie takes the top dish from the dirty stack, applies soap, and then places it onto the table. When placing this dish on the table, Bessie may only place it on top of an existing non-empty stack of dishes, or start a new stack on the far right. - Elsie takes the top dish from the leftmost stack on the table, rinses it, and then places it on top of the clean stack. They want the clean stack to be sorted by label, with the smallest label at the bottom and the largest label at the top. However, they find that sometimes this is not possible. Now, given the stacking order of the dirty dishes, find the maximum prefix such that after washing all dishes in this prefix, they can be stacked according to the requirement above.

The first line contains an integer $N$ ($1 \leq N \leq 10^5$). The next $N$ lines each contain one integer, representing the stacking order of Bessie's dirty dish stack. The first dish given in the input is at the top of the stack.

Output the length of the maximum prefix of the sequence such that after washing all dishes in this prefix, they can be stacked with smaller labels at the bottom and larger labels at the top.

Translated by ChatGPT 5