#P17987. Deque Sort
Deque Sort
Deque Sort
题目描述
给定 的一个排列 。机器按轮进行排序,每一轮将当前排列按如下规则放入一个新的双端队列:
- 将 放入空队列。
- 按顺序处理 。若当前元素大于队列最右端的元素,将它放到队尾;否则放到队首。
本轮得到的队列就是新排列。如果排列已经升序排列,机器立即停止;否则继续下一轮。初始排列已升序时,机器执行 轮。
回答 个查询 :完成 轮后,从左往右第 个元素是什么?如果机器总共执行的轮数小于 ,回答 。
输入格式
第一行两个整数 。第二行 个整数,表示初始排列。
接下来 行,每行两个整数 ,表示一个查询。
输出格式
输出 行,每行一个整数,依次回答查询。 表示查询初始排列。
数据范围
; 是 到 的排列;,。
样例 1 输入
5 4
2 1 3 5 4
1 1
3 2
4 1
0 4
样例 1 输出
4
2
-1
5
机器依次得到 、、,共执行三轮。
样例 2 输入
1 1
1
1 1
样例 2 输出
-1