Вам дан массив целых чисел \(a_1,\ldots, a_n\), где \(1\le a_i \le n\) для всех \(i\).
Так же есть функция «замены» \(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=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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
2 5 4 1 3
4 4
1 5
1 4
3 5
4 5
2 3
|
-1
0
1
2
3
4
|
|
2
|
6 3
2 3 4 6 1 2
5 6
2 5
2 3
|
5
1
3
|
|
3
|
5 3
3 2 2 4 1
2 5
1 3
1 5
|
-1
-1
0
|