Двое странников выпали из реальности в Закулисье (Backrooms), уровни которого пронумерованы неотрицательными целыми числами. Сначала они только поднимались по уровням, потом в один и тот же час оказались на одном уровне и дальше только спускались. Номер своего уровня в Закулисье узнать нельзя, поэтому каждый час странники записывали в журнал лишь, на сколько уровней первый выше второго.

Более формально, массив неотрицательных целых чисел $$$h_1, h_2, \ldots, h_m$$$ называется горой с вершиной $$$k$$$, если $$$h_1 \le h_2 \le \ldots \le h_k \ge h_{k+1} \ge \ldots \ge h_m$$$. Пусть поход длился $$$m$$$ часов и в $$$i$$$-й час первый странник был на уровне $$$a_i$$$, а второй — на уровне $$$b_i$$$. Тогда $$$a$$$ и $$$b$$$ — горы с одной и той же вершиной $$$k$$$, $$$a_k = b_k$$$, а в журнал записаны числа $$$d_i = a_i - b_i$$$ при $$$i = 1, \ldots, m$$$.

В руки исследователей Закулисья попал журнал из $$$n$$$ записей $$$c_1, c_2, \ldots, c_n$$$, но какие из них относятся к походу, неизвестно. У исследователей есть $$$q$$$ независимых гипотез: каждая задаётся числами $$$l$$$ и $$$r$$$ и означает, что поход длился $$$m = r - l + 1$$$ часов и $$$d_i = c_{l+i-1}$$$. Для каждой гипотезы определите, могла ли она быть верной, и если могла — на каком наименьшем уровне странники могли встретиться.