F. Холмы и ямы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В пустынном городе с холмистым ландшафтом мэрия решила выровнять поверхность дороги, закупив самосвал. Дорога разделена на $$$n$$$ участков, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Высота поверхности на $$$i$$$-м участке равна $$$a_i$$$. Если высота $$$i$$$-го участка больше $$$0$$$, то самосвал должен забрать песок с $$$i$$$-го участка дороги, а если высота $$$i$$$-го участка меньше $$$0$$$, то самосвал должен засыпать песком яму на $$$i$$$-м участке дороги. Гарантируется, что изначальные высоты не равны $$$0$$$.

Когда самосвал находится на $$$i$$$-м участке дороги, он может либо забрать оттуда $$$x$$$ единиц песка, и тогда высота поверхности на $$$i$$$-м участке уменьшится на $$$x$$$, либо засыпать туда $$$x$$$ единиц песка (при условии, что у него в кузове сейчас есть хотя бы $$$x$$$ единиц песка), и тогда высота поверхности на $$$i$$$-м участке дороги увеличится на $$$x$$$.

Самосвал может начать свой путь на любом участке дороги. Перемещение на соседний слева или справа участок дороги занимает $$$1$$$ минуту, при этом временем загрузки и разгрузки песка можно пренебречь. Кузов самосвала имеет бесконечную вместимость и изначально пуст.

Вам нужно найти минимальное время, за которое самосвал сможет выровнять песок так, чтобы высота на каждом участке стала равна $$$0$$$. Обратите внимание, что после всех передвижений в кузове самосвала может остаться песок. Вам нужно решить эту задачу независимо, если оставить только участки с номерами от $$$l_i$$$ до $$$r_i$$$. При этом использовать песок вне отрезка нельзя.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — количество участков и количество запросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \neq 0$$$) — изначальная высота на каждом участке.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы отрезка участков, для которого нужно определить минимальное время.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого запроса выведите минимальное время, необходимое, чтобы выровнять песок на отрезке $$$[l_i, r_i]$$$, или $$$-1$$$, если это невозможно.

Пример
Входные данные
5
1 1
-179
1 1
5 3
-2 2 -1 3 -1
2 4
1 5
1 3
7 1
1 1 1 -4 1 1 1
1 7
7 2
2 -2 2 -2 1 2 -1
1 7
2 7
4 4
1000000000 1000000000 999999999 -1000000000
2 4
3 4
2 3
1 3
Выходные данные
-1
2
5
-1
8
6
6
2
-1
1
2
Примечание

В первом наборе входных данных нужно добавить $$$179$$$ единиц песка на единственном участке. Но забрать их неоткуда, поэтому это невозможно.

Во втором наборе входных данных:

  • В первом запросе самосвал может начать путь на втором участке. Он может забрать $$$2$$$ единицы песка, после чего на втором участке высота станет равна $$$0$$$. Затем самосвал может переехать на третий участок. Он может высыпать туда $$$1$$$ единицу песка, после чего на третьем участке высота станет равна $$$0$$$. Затем самосвал может переехать на четвёртый участок. Там он может забрать $$$3$$$ единицы песка, после чего на четвёртом участке высота станет равна $$$0$$$. Суммарно самосвал потратит на перемещения $$$2$$$ минуты.
  • Во втором запросе самосвал может начать путь на четвёртом участке. Он может забрать $$$3$$$ единицы песка, после чего на четвёртом участке высота станет равна $$$0$$$. Затем самосвал может переехать на пятый участок. Он может высыпать туда $$$1$$$ единицу песка, после чего на пятом участке высота станет равна $$$0$$$. Затем самосвал может переехать на четвёртый участок, а потом на третий. Он может высыпать $$$1$$$ единицу песка, после чего на третьем участке высота станет равна $$$0$$$. Затем самосвал может переехать на второй участок. Он может забрать $$$2$$$ единицы песка. Затем он может переехать на первый участок. Он может высыпать $$$2$$$ единицы песка, после чего на первом участке высота станет равна $$$0$$$. Суммарно самосвал потратит на перемещения $$$5$$$ минут.
  • В третьем запросе самосвал не сможет сделать высоту на каждом участке равной $$$0$$$.