После тяжёлого рабочего дня Казимир Казимирович решил отдохнуть, погуляв по лесу. Замученный дорогой, он выбился из сил. И в доме лесника он ночлега попросил. С улыбкой добродушной старик его впустил.

Теперь уставшего путника нужно хорошенько накормить. У лесника дома, к счастью, оказалось $$$n$$$ блюд, каждое из которых характеризуется своей пищевой ценностью $$$a_i$$$. Добрый лесник запланировал для Казимира Казимировича $$$q$$$ обедов, на обеде с номером $$$j$$$ лесник может попробовать все блюда с номерами от $$$l_j$$$ до $$$r_j$$$. Для обеда введем понятие насыщенности — минимальное значение $$$a_i - i$$$ по всем блюдам, разрешенным на данном обеде.

Так как Казимир Казимирович — уважающий себя путник, он хочет максимизировать насыщенность каждого обеда, поэтому перед началом каждого приема пищи он может незаметно поменять порядок блюд из разрешенного отрезка (обратите внимание, что в таком случае номер некоторых блюд может измениться). Другими словами, Казимир Казимирович может заменить значения $$$a_l, a_{l + 1}, ..., a_{r - 1}, a_{r}$$$ на любую перестановку этих значений, а уже потом посчитать насыщенность обеда.

Но Казимир Казимирович также очень благодарный путник, поэтому после каждого обеда он возвращает все блюда на исходные места. Другими словами, перед каждым обедом значения блюд $$$a_l, a_{l + 1}, ..., a_{r - 1}, a_{r}$$$ должны быть такими же, как изначально, и перестановка этих значений на текущем обеде никак не влияет на следующие обеды.

Для каждого из обедов определите его максимально возможную насыщенность.

Напомним, что перестановкой чисел называется любое их переупорядочивание, например для массива $$$[1, 5, 6]$$$ это могут быть $$$[1, 5, 6]$$$, $$$[1, 6, 5]$$$, $$$[5, 1, 6]$$$, $$$[5, 6, 1]$$$, $$$[6, 1, 5]$$$, $$$[6, 5, 1]$$$.