Вам дан массив целых чисел $$$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)$$$, или определить, что это невозможно.