CF1707E.Replace

You are given an integer array $a_1,\ldots, a_n$, where $1\le a_i \le n$ for all $i$.

There's a "replace" function $f$ which takes a pair of integers $(l, r)$, where $l \le r$, as input and outputs the pair $$f\big( (l, r) \big)=\left(\min\{a_l,a_{l+1},\ldots,a_r\},\, \max\{a_l,a_{l+1},\ldots,a_r\}\right).$$

Consider repeated calls of this function. That is, from a starting pair $(l, r)$ we get $f\big((l, r)\big)$, then $f\big(f\big((l, r)\big)\big)$, then $f\big(f\big(f\big((l, r)\big)\big)\big)$, and so on.

Now you need to answer $q$ queries. For the $i$-th query you have two integers $l_i$ and $r_i$ ($1\le l_i\le r_i\le n$). You must answer the minimum number of times you must apply the "replace" function to the pair $(l_i,r_i)$ to get $(1, n)$, or report that it is impossible.

给你一个整数数组 $a_1,\ldots, a_n$，其中对所有 $i$ 均满足 $1\le a_i \le n$。

定义一个“替换”函数 $f$，其输入为一对整数 $(l, r)$（满足 $l \le r$），输出为

$$f\big( (l, r) \big)=\left(\min\{a_l,a_{l+1},\ldots,a_r\},\, \max\{a_l,a_{l+1},\ldots,a_r\}\right).$$

考虑对该函数进行重复调用：即从初始对 $(l, r)$ 出发，依次得到 $f\big((l, r)\big)$、$f\big(f\big((l, r)\big)\big)$、$f\big(f\big(f\big((l, r)\big)\big)\big)$，依此类推。

现在你需要回答 $q$ 个查询。对于第 $i$ 个查询，给定两个整数 $l_i$ 和 $r_i$（满足 $1\le l_i\le r_i\le n$），你必须求出：将“替换”函数作用于 $(l_i,r_i)$ 所需的最少次数，使得结果恰好为 $(1, n)$；若不可能达到 $(1, n)$，则报告不可能。

The first line contains two positive integers $n$, $q$ ($1\le n,q\le 10^5$) — the length of the sequence $a$ and the number of the queries.

The second line contains $n$ positive integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$) — the sequence $a$.

Each line of the following $q$ lines contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — the queries.

第一行包含两个正整数 $n$、$q$（$1\le n,q\le 10^5$）——分别表示序列 $a$ 的长度和查询的数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）——即序列 $a$。

接下来的 $q$ 行中，每行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$）——表示一次查询。

For each query, output the required number of times, or $-1$ if it is impossible.

对于每个查询，输出所需的次数；如果不可能，则输出 $-1$。

In the first example, $n=5$ and $a=[2,5,4,1,3]$.

For the first query: $(4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots$, so it's impossible to get $(1,5)$.

For the second query, you already have $(1,5)$.

For the third query: $(1,4)\to(1,5)$.

For the fourth query: $(3,5)\to(1,4)\to(1,5)$.

For the fifth query: $(4,5)\to(1,3)\to(2,5)\to(1,5)$.

For the sixth query: $(2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5)$.

在第一个例子中，$n=5$ 且 $a=[2,5,4,1,3]$。

对于第一个查询：$(4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots$，因此无法得到 $(1,5)$。

对于第二个查询，你已经拥有 $(1,5)$。

对于第三个查询：$(1,4)\to(1,5)$。

对于第四个查询：$(3,5)\to(1,4)\to(1,5)$。

对于第五个查询：$(4,5)\to(1,3)\to(2,5)\to(1,5)$。

对于第六个查询：$(2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5)$。