Фермер Джон хочет справедливо разделить пакеты сена между его двумя
любимыми коровами Беси и Эльза. У него есть \(N\) ( \(1\le N\le 2\cdot 10^5\))
пакетов сена, упорядоченных в невозрастающем порядке. Где \(i\)-ый пакет
сена имеет \(a_i\) единиц сена ($2\cdot 10^5\ge a1\ge a2 \ge \dots
\ge aN \ge 1$).
ФД хочет разделить непрерывный отрезок пакетов \(a_l, \dots, a_r\)
между Беси и Эльзой, рассматривая пакеты в порядке от \(l\) до \(r\),
и когда рассматривает \(i\)-ый пакет он даёт его корове, у которой сейчас
меньше сена. Если равно - даёт Беси.
Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый описывается
тремя целыми числами \(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)).
Для каждого запроса, введите на сколько больше единиц сена будет у Беси,
после обработки пакетов от \(l\) до \(r\), если Беси начнёт с количеством сена
на \(x\) единиц больше чем у Эльзы. Заметим эта величина отрицательна, если
вначале у Эльзы будет на \(x\) единиц больше чем у Беси.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит \(a_1\dots a_N\).
Третья строка содержит \(Q\).
Следующие \(Q\) строк содержат \(l, r, x\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(Q\) строк, содержащих ответ на каждый запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2
|
1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1
|