Flipping Stacks (APCS 2025-11 Advanced)

You are given a permutation \(P = (p_1, p_2, \ldots, p_n)\) containing each integer from \(1\) to \(n\) exactly once.

There are two stacks \(S_1\) and \(S_2\). Initially, \(S_1\) is empty, and \(S_2\) contains \(p_1, p_2, \ldots, p_n\) from top to bottom. In other words, \(p_1\) is on top of \(S_2\), and \(p_n\) is at the bottom.

In one operation, you choose one non-empty stack and pop its top element. If this element is exactly the next number that must be output, you output it. Otherwise, you must push it onto the other stack.

Your goal is to output \(1, 2, \ldots, n\) in order. Compute the minimum number of pop operations needed.

Input

The first line contains an integer \(n\).

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\), representing the permutation \(P\).

Constraints

• \(1 \le n \le 10^5\)
• \(P\) is a permutation of \(1\) through \(n\)

Output

Output one integer: the minimum number of pop operations needed.

Scoring

The time limit for every test case is 1 second. The score is the sum of the independently passed test cases.

Sample Input 1

3
3 1 2

Sample Output 1

4

Sample Explanation 1

At first, the top of \(S_2\) is \(3\). Pop \(3\) and push it onto \(S_1\), then pop and output \(1, 2\) from \(S_2\), and finally pop and output \(3\) from \(S_1\). This uses \(4\) pop operations.

Sample Input 2

4
3 2 4 1

Sample Output 2

8

Sample Explanation 2

One optimal sequence of operations is:

pop 3 and push it onto the other stack
pop 2 and push it onto the other stack
pop 4 and push it onto the other stack
pop and output 1
pop 4 and push it onto the other stack
pop and output 2
pop and output 3
pop and output 4

Therefore, the answer is \(8\).

Source

2025 November APCS Advanced Programming Implementation, Problem 3: ZeroJudge r628, Flipping Stacks.