В пустынном городе с холмистым ландшафтом мэрия решила выровнять поверхность дороги, закупив самосвал. Дорога разделена на \(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\). При этом использовать песок вне отрезка нельзя.
Выходные данные
Для каждого запроса выведите минимальное время, необходимое, чтобы выровнять песок на отрезке \([l_i, r_i]\), или \(-1\), если это невозможно.
Примечание
В первом наборе входных данных нужно добавить \(179\) единиц песка на единственном участке. Но забрать их неоткуда, поэтому это невозможно.
Во втором наборе входных данных:
- В первом запросе самосвал может начать путь на втором участке. Он может забрать \(2\) единицы песка, после чего на втором участке высота станет равна \(0\). Затем самосвал может переехать на третий участок. Он может высыпать туда \(1\) единицу песка, после чего на третьем участке высота станет равна \(0\). Затем самосвал может переехать на четвёртый участок. Там он может забрать \(3\) единицы песка, после чего на четвёртом участке высота станет равна \(0\). Суммарно самосвал потратит на перемещения \(2\) минуты.
- Во втором запросе самосвал может начать путь на четвёртом участке. Он может забрать \(3\) единицы песка, после чего на четвёртом участке высота станет равна \(0\). Затем самосвал может переехать на пятый участок. Он может высыпать туда \(1\) единицу песка, после чего на пятом участке высота станет равна \(0\). Затем самосвал может переехать на четвёртый участок, а потом на третий. Он может высыпать \(1\) единицу песка, после чего на третьем участке высота станет равна \(0\). Затем самосвал может переехать на второй участок. Он может забрать \(2\) единицы песка. Затем он может переехать на первый участок. Он может высыпать \(2\) единицы песка, после чего на первом участке высота станет равна \(0\). Суммарно самосвал потратит на перемещения \(5\) минут.
- В третьем запросе самосвал не сможет сделать высоту на каждом участке равной \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|