#P17987. Deque Sort

Deque Sort

Deque Sort

题目描述

给定 1,2,…,n1,2,\ldots,n 的一个排列 aa。机器按轮进行排序,每一轮将当前排列按如下规则放入一个新的双端队列:

  1. 将 a1a_1 放入空队列。
  2. 按顺序处理 a2,…,ana_2,\ldots,a_n。若当前元素大于队列最右端的元素,将它放到队尾;否则放到队首。

本轮得到的队列就是新排列。如果排列已经升序排列,机器立即停止;否则继续下一轮。初始排列已升序时,机器执行 00 轮。

回答 qq 个查询 (t,b)(t,b):完成 tt 轮后,从左往右第 bb 个元素是什么?如果机器总共执行的轮数小于 tt,回答 −1-1。

输入格式

第一行两个整数 n,qn,q。第二行 nn 个整数,表示初始排列。

接下来 qq 行,每行两个整数 ti,bit_i,b_i,表示一个查询。

输出格式

输出 qq 行,每行一个整数,依次回答查询。ti=0t_i=0 表示查询初始排列。

数据范围

1≤n,q≤5×1051\le n,q\le5\times10^5;aa 是 11 到 nn 的排列;0≤ti≤1090\le t_i\le10^9,1≤bi≤n1\le b_i\le n。

样例 1 输入

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

样例 1 输出

4
2
-1
5

机器依次得到 (4,1,2,3,5)(4,1,2,3,5)、(3,2,1,4,5)(3,2,1,4,5)、(1,2,3,4,5)(1,2,3,4,5),共执行三轮。

样例 2 输入

1 1
1
1 1

样例 2 输出

-1