题目描述

小明刚学会二分查找。老师给了他一个单调的整数序列 —— 要么从头到尾不减（后一个不小于前一个），要么从头到尾不增（后一个不大于前一个）。

现在有 $m$ 次询问，每次给出一个操作编号 $op$ 和一个整数 $x$，要找的元素如下：

$op$	要找的元素
1	所有严格大于 $x$ 的元素中，最小的那个
2	所有大于等于 $x$ 的元素中，最小的那个
3	所有严格小于 $x$ 的元素中，最大的那个
4	所有小于等于 $x$ 的元素中，最大的那个

因为序列是单调的，满足条件的元素一定占据连续的一段， 而要找的就是这一段最靠近分界处的那个端点。具体来说：

$op$	$t=1$（不减）时输出	$t=2$（不增）时输出
1	第一个满足 $a_i > x$ 的下标 $i$	最后一个满足 $a_i > x$ 的下标 $i$
2	第一个满足 $a_i \ge x$ 的下标 $i$	最后一个满足 $a_i \ge x$ 的下标 $i$
3	最后一个满足 $a_i < x$ 的下标 $i$	第一个满足 $a_i < x$ 的下标 $i$
4	最后一个满足 $a_i \le x$ 的下标 $i$	第一个满足 $a_i \le x$ 的下标 $i$

请输出这个位置（下标从 $1$ 开始，按输入序列本身的顺序数）。 如果序列中不存在满足条件的元素，输出 -1。

输入格式

第一行三个整数 $n$、$m$、$t$。其中 $t=1$ 表示序列单调不减，$t=2$ 表示序列单调不增。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行，每行两个整数 $op$ 和 $x$，含义见上表。

输出格式

共 $m$ 行，每行一个整数，表示对应询问的答案。

输入样例 1

5 8 1
1 3 3 3 5
1 3
2 3
3 3
4 3
1 5
2 6
3 1
4 0

输出样例 1

5
2
1
4
-1
-1
-1
-1

样例 1 解释

序列是 1 3 3 3 5，单调不减。

询问	满足条件的下标	取哪一端	答案
1 3	$>3$ 的：5	第一个	5
2 3	$\ge 3$ 的：2, 3, 4, 5		2
3 3	$<3$ 的：1	最后一个	1
4 3	$\le 3$ 的：1, 2, 3, 4		4
1 5	$>5$ 的：没有	—	-1
2 6	$\ge 6$ 的：没有
3 1	$<1$ 的：没有
4 0	$\le 0$ 的：没有

输入样例 2

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

输出样例 2

1
4
5
2

样例 2 解释

序列是 5 3 3 3 1，单调不增。它由样例 1 的序列翻转而来，四个询问也完全相同， 但答案全都变了 —— 因为序列方向反过来之后，"靠近分界处的那一端"也跟着换到了另一头。

询问	满足条件的下标	取哪一端	答案
1 3	$>3$ 的：1	最后一个	1
2 3	$\ge 3$ 的：1, 2, 3, 4		4
3 3	$<3$ 的：5	第一个	5
4 3	$\le 3$ 的：2, 3, 4, 5		2

数据范围

测试点	$n,\ m$	特点
1 ~ 2	同两个样例
3 ~ 8	$\le 1000$	含 $n=1$、元素全部相同、严格单调等边界
9 ~ 14	$\le 10^5$	不减、不增各占一半
15 ~ 20	$\le 2\times 10^5$	含大量重复元素、取值达到 $\pm 10^9$

对于 $100\%$ 的数据：$1 \le n, m \le 2\times 10^5$，$-10^9 \le a_i, x \le 10^9$， $op \in \{1,2,3,4\}$，$t \in \{1,2\}$，且保证序列按 $t$ 指定的方向单调。

提示

四种边界写起来只差一个不等号，但差一位就全错。 你只需要两个二分模板：「第一个 $\ge x$ 的位置」和「最后一个 $\le x$ 的位置」， 另外两种可以想办法用它们凑出来（提示：$a_i$ 都是整数）。 至于"不增"的序列，与其重写一套二分，不如想想能不能先把它变成"不减"。