You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在 R 国，每个城市有两个编号 $(x,y)$，其中 $x,y$ 都是 $[n]$ 内且 $x\leq y$ 的数，并且城市 $(1,n)$ 是穗织，即 R 国的首都。

R 国交通十分不便，每个城市只有一条走向其他城市的道路。具体的，R 国交通部有一个长度为 $n$ 的序列 $a_1,\dots,a_n$。那么规定 $(l,r)$ 只能前往 $(\min_{l\leq i\leq r}a_i,\max_{l\leq i\leq r}a_i)$。

小 I 在城市 $(x,y)$，你需要告诉小 I 他需要走多少的路才能到达穗织，或者说明不可能。

输入格式

本题单点含有多组测试样例。

第一行一个正整数 $T$ 表示测试点数目。

每个测试点，第一行两个正整数表示 $n,q$。

接下来长度为 $n$ 的序列表示 $a_i$。

接下来 $q$ 行，每行两个正整数 $x,y$ 表示一组询问。

输出格式

每个测试样例，$q$ 行，如果可能输出最小步数，否则输出 -1。

测试样例

样例解释

下发样例依次和 $2,5,8,10$ 使用同样的生成器制造。

数据范围

对于所有数据，保证 $\sum n,\sum q\leq 10^6,1\leq a_i\leq n$。详细数据范围见下方：