Description

"I'm here to end the band"

A girl band is taking a group photo, but the photographer has bad intentions. She plans to process the photos and then post them on social media, causing dissatisfaction among fans, which will cause the popularity of some members of the band to rise or fall. She thinks this will end the band. Her plan is as follows:

It is known that the girl band has $n$ members, who are lined up from left to right for the photo. The initial popularity ranking of each member is different, ranging from $1$ to $n$. The photographer plans to take $k$ photos and publish them on social media after each photo. Each of her photos only contains a continuous section of the band member permutation, so that the fans of the most popular member who does not appear in this photo will be extremely angry and quit following her, causing the ranking of this member to drop by one (the original ranking of the member who was one lower will rise). Through $k$ operations, she successfully disrupted the ranking of the band members, and her goal was achieved.

But now she has a problem because there are too many members in the band; for each captured photo, she can't judge which member who doesn't appear ranks first, so she turned to you for help, hoping you can help her solve the problem.

Formally, given a permutation $a_1, a_2, \dots, a_n$ from $1$ to $n$, perform $k$ operations, each operation:

• Given an interval $[l,r]$, find the smallest positive integer that does not appear in the interval $[l,r]$ in the current permutation, and set this number to $x$ (i.e. $x=\min\{p\mid \forall i \in [l,r],p\neq a_i,p\geq 1\}$);
• If $x<n$, output $x$, and swap the positions of the numbers $x$ and $x+1$ in the current permutation $a_1, a_2, \dots, a_n$;
• If $x\ge n$, output the string $\tt{peace}$.

Wherein, the permutation $a_1, a_2, \dots, a_n$ from $1$ to $n$ refers to a set of numbers that satisfies $\{a_1, a_2, \dots, a_n\} = \{1, 2, \dots n\}$.

Input Format

The first line contains a positive integer $n$ ($1\le n\le 5\times 10^5$), indicating the size of the permutation.

The second line contains $n$ positive integers $a_i$, separated by a space, indicating the initial permutation $a_1, a_2, \dots, a_n$ ($\{a_1, a_2, \dots, a_n\} = \{1, 2, \dots n\}$).

The third line contains a positive integer $k$ ($1\le k\le 10^5$), indicating the number of operations.

The next $k$ lines, each containing two positive integers $l$ and $r$ ($1\le l\le r\le n$), separated by a space, indicate the range of operations.

Output Format

For each operation in each test data, give the answer and perform the modification.

Remember that the smallest positive integer that does not appear in the interval $[l,r]$ in the permutation $a_1, a_2, \dots, a_n$ is $x$:

• If $x<n$, output $x$ and swap the positions of the numbers $x$ and $x+1$ in the current permutation $a_1, a_2, \dots, a_n$;
• If $x\ge n$, output the string $\tt{peace}$.

5
4 3 1 2 5
5
2 4
2 5
1 3
1 3
1 5

4
peace
2
3
peace

10
10 9 4 3 2 1 6 5 8 7
3
1 10
2 9
3 9

peace
7
8

Hint

For the first sample:

The first operation is $[2,4]$, and the current permutation is $4,3,1,2,5$.

The smallest positive integer that does not appear in the interval $[2,4]$ is $4$. Output $4$ and swap the positions of $4$ and $5$ in the permutation.

The second operation is $[2,5]$, and the current permutation is $5,3,1,2,4$.

The smallest positive integer that does not appear in the interval $[2,5]$ is $5$. Output $\tt{peace}$, and the permutation remains unchanged.

The third operation is $[1,3]$, and the current permutation is $5,3,1,2,4$.

The smallest positive integer that does not appear in the interval $[1,3]$ is $2$. Output $2$ and swap the positions of $2$ and $3$ in the permutation.

The fourth operation is $[1,3]$, and the current permutation is $5,2,1,3,4$.

The smallest positive integer that does not appear in the interval $[1,3]$ is $3$. Output $3$ and swap the positions of $3$ and $4$ in the permutation.

The fifth operation $[1,5]$, the current permutation is $5,2,1,4,3$.

The smallest positive integer that does not appear in the interval $[1,5]$ is $6$. Output $\tt{peace}$, the permutation remains unchanged.