首当其冲

题目描述

Orange在玩一个卡牌游戏，双方轮流出牌，必须保证每一轮的卡牌都比对方点数大。同时，每个人的手牌都是有序的，假设你选择的第 $p$ 张牌是一张满足条件的牌，你要打出它，就会失去它前方的所有牌。双方谁先失去所有牌或者无法出牌，则会输掉游戏。

因此，为了尽量避免输掉游戏，假设对方出的牌点数为 $v$，Orange想要你找出在卡牌点数序列 $a[l,...,r]$ 中从左边开始第一张点数大于 $v$ 的牌的位置，如果不存在这样的牌，则输出-1。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行为两个整数 $n, m$，表示代表卡牌点数的序列 $a_i$ 和Orange的询问次数。 第二行为 $n$ 个整数，表示序列 $a_i$。 接下来 $m$ 行，每行3个整数 $l, r, v$，表示一次查询。

数据范围

$1 \le n, m \le 10^5$ $1 \le a_i,v \le 10^9$ $1 \le l \le r \le n$ $\sum n,m \le 3\times 10^5$

输出格式

对于每次询问，输出一个答案，占一行。

样例 #1

样例输入 #1

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

样例输出 #1

2
4
-1

提示

样例解释

对于序列 $a = [2,4,1,3,2]$: 第一次询问，$a_1 \sim a_3$ 中，第一个比 $2$ 大的数为 $a_2=4$，其位置为 $2$。 第二次询问，$a_3 \sim a_5$ 中，第一个比 $2$ 大的数为 $a_4=3$，其位置为 $4$。 第二次询问，$a_2 \sim a_3$ 中，不存在比 $4$ 大的数，因此答案为$-1$。