题目描述

「我是来结束乐队的」

某个少女乐队正在进行合照，可摄影师不怀好意，她打算对拍出的照片进行处理后再发布社交媒体，引起粉丝们的不满，这会导致乐队中某些成员人气的升降。她觉得这样就能结束这支乐队了。她的计划如下：

已知少女乐队有 $n$ 个成员，从左到右排成一排照相，其中每个成员的初始人气排名并不相同，分别从排名第 $1$ 到第 $n$。摄影师打算拍 $k$ 张照片并在每次拍完之后公开到社交媒体，她的每张照片只包含乐队成员排列中连续的一段，这样这段照片中未出现成员中的人气排名最靠前的成员的粉丝就会红温脱粉，导致这名成员的排名下降一名（原低一名的成员排名会上升）。通过 $k$ 次操作，她成功打乱了乐队成员的排名，她的目的就达到了。

但现在她遇到了一个问题，因为乐队的成员太多了，对于每次截取下来的某一段照片，她不能判断哪个未出现的成员排名最靠前，所以她求助于你，希望你帮她解决问题。

形式化的，给定一个从 $1$ 到 $n$ 的排列 $a_1, a_2, \dots, a_n$，进行 $k$ 次操作，每次操作：

• 给定一个区间 $[l,r]$，求 当前排列中区间 $[l,r]$ 上未出现的最小正整数 是多少，并设此数为 $x$（即 $x=\min\{p\mid \forall i \in [l,r],p\neq a_i,p\geq 1\}$）；
  • 若 $x<n$，则输出 $x$，并交换当前排列 $a_1, a_2, \dots, a_n$ 中数字 $x$ 与 $x+1$ 的位置；
  • 若 $x\ge n$，则输出字符串 $\tt{peace}$。

其中，从 $1$ 到 $n$ 的排列 $a_1, a_2, \dots, a_n$，是指满足 $\{a_1, a_2, \dots, a_n\} = \{1, 2, \dots n\}$ 的一组数。

输入格式

第一行包含一个正整数 $n$ ($1\le n\le 5\times 10^5$)，表示排列的大小。

第二行包含 $n$ 个正整数 $a_i$，用一个空格分隔，表示初始排列 $a_1, a_2, \dots, a_n$ ($\{a_1, a_2, \dots, a_n\} = \{1, 2, \dots n\}$)。

第三行一个正整数 $k$ ($1\le k\le 10^5$)，表示操作的次数。

接下来 $k$ 行，每行两个正整数 $l$ 和 $r$ ($1\le l\le r\le n$)，用一个空格分隔，表示操作的区间。

输出格式

对于每个测试数据中的每次操作，给出答案，并执行修改。

记排列 $a_1, a_2, \dots, a_n$ 在区间 $[l,r]$ 上未出现的最小正整数为 $x$：

• 若 $x<n$，则输出 $x$，并交换当前排列 $a_1, a_2, \dots, a_n$ 中数字 $x$ 与 $x+1$ 的位置；
• 若 $x\ge n$，则输出字符串 $\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

提示

对于第一组样例：

第一次操作 $[2,4]$，当前排列为 $4,3,1,2,5$。

区间 $[2,4]$ 内未出现的最小正整数为 $4$，输出 $4$ 并交换排列中 $4$ 和 $5$ 的位置。

第二次操作 $[2,5]$，当前排列为 $5,3,1,2,4$。

区间 $[2,5]$ 内未出现的最小正整数为 $5$，输出 $\tt{peace}$，排列不变。

第三次操作 $[1,3]$，当前排列为 $5,3,1,2,4$。

区间 $[1,3]$ 内未出现的最小正整数为 $2$，输出 $2$ 并交换排列中 $2$ 和 $3$ 的位置。

第四次操作 $[1,3]$，当前排列为 $5,2,1,3,4$。

区间 $[1,3]$ 内未出现的最小正整数为 $3$，输出 $3$ 并交换排列中 $3$ 和 $4$ 的位置。

第五次操作 $[1,5]$，当前排列为 $5,2,1,4,3$。

区间 $[1,5]$ 内未出现的最小正整数为 $6$，输出 $\tt{peace}$，排列不变。