$N$ коров Farmer John ($1 \le N \le 50,000$) ежедневно стоят на доение одинаково. Однажды он играет с частью в алтимат-фрисби. Для простоты выбирает непрерывный отрезок очереди, но для общего веселья рост не должен сильно отличаться.

Есть $Q$ ($1 \le Q \le 200,000$) возможных групп и рост ($1 \le height \le 1,000,000$). Для каждой найдите разность максимального и минимального роста.

Входные данные

Читайте со стандартного ввода.

Строка 1: целые $N$, $Q$ через пробел.

Строки $2..N+1$: строка $i+1$ — целый рост коровы $i$.

Строки $N+2$..$N+Q+1$: целые $A$, $B$ ($1 \le A \le B \le N$), диапазон $A$–$B$ включительно.

Выходные данные

Пишите в стандартный вывод.

Строки $1..Q$: по целому — ответ на запрос, разность высокого и низкого в диапазоне.

Примеры

Входные данные 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Выходные данные 1

6
3
0

Источник: USACO, январь 2007, серебро