题目描述

WDG 现在需要检查一段输入是否符合规范。 这段输入为一个包含 $n$ 个整数的数组 $A$。 WDG 一共要进行 $Q$ 次检查，每次检查 WDG 会在下方两种情况中选择一种确认：

• 情况 $1$： $A$ 数组内是否存在一个大于等于 $X$ 的数，如果存在， WDG 需要找到第一个出现的数的位置。
• 情况 $2$： $A$ 数组内是否存在一个小于等于 $X$ 的数，如果存在， WDG 需要找到最后一个出现的数的位置。

输入格式

第一行包含 $2$ 个正整数，分别是 $n, Q$。

第二行包含 $n$ 个整数，第 $i$ 个数为 $A_i$。

接下来一共 $Q$ 行，每行包含两个整数，第一个数为$op$，即确认的情况为 $1$ 或者 $2$。第二个数为 $X$

输出格式

每次检查单独一行，输出所要找到的位置，如果不存在，输出 $−1$。

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

1
2
7
7
3
5

数据范围

对于数据点 $1 ∼ 5$， $n, Q ≤ 1000$。

对于数据点 $6 ∼ 10$， $A$ 保持单调性（单调递增或者单调递减）， $op = 1$

对于数据点 $11 ∼ 14$， $op = 1$

对于数据点 $15 ∼ 20$，无特殊性质。

对于 $100\%$ 的数据， $n, Q ≤ 5 × 10^5; −10^9 ≤ A_i, x ≤ 10^9; op ∈ {1, 2}$