29140번 - Волейбол 다국어

Во время урока физкультуры Фоме в очередной раз понадобилось съездить по очень важному делу. Но он не может уехать просто так, оставив детей без занятия, чтобы они не разбрелись по школе и не выдали его отсутствие во время урока. Поэтому он придумал очередную экзекуцию для своих учеников.

На территории школы находятся $n$ столбиков, которые стоят в ряд c промежутком в один метр, $i$-й из которых имеет высоту $a_i$. Между двумя столбиками можно натянуть сетку для игры в волейбол, если их высоты равны, и между ними нет столбика с большей высотой. Каждому своему ученику Фома назначил какой-то интервал столбиков. От ученика же требуется найти наибольшую длину сетки, которую можно натянуть на этом интервале. Длина сетки вычисляется как расстояние между столбиками, между которыми она натянута.

Ребята поняли, что на выполнение этой задачи у них уйдет масса времени, поэтому они просят вас помочь им.

В первой строке входного файла даны два числа $n$ и $m$ ($1 \le n \le 2 \cdot 10^5; 1 \le m \le 2 \cdot 10^5$) --- количество столбиков на территории школы и количество учеников Фомы. В следующей строке заданы $n$ целых положительных чиcел $a_i$ ($1 \le a_i \le 10^9$) --- высоты столбиков. В следующих $m$ строках заданы по два числа $l$ и $r$ ($1 \le l \le r \le n$) --- заданные ребятам интервалы.

В выходной файл выведите $m$ строк, в $i$-й строке выведите ответ для $i$-го ученика.