G. Clubstep
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Существует чрезвычайно сложная видеоигра, которая является одной из любимых видеоигр Чанеки. Один из самых трудных уровней в игре называется Clubstep. Clubstep состоит из $$$n$$$ частей, пронумерованных от $$$1$$$ до $$$n$$$. Чанека хорошо натренировалась в прохождении уровня, поэтому на данный момент ее уровень знакомства с каждой частью $$$i$$$ составляет $$$a_i$$$.

После этого Чанека может сделать несколько (возможно, ноль) попыток пройти Clubstep. В каждой попытке она погибает на одной из $$$n$$$ частей. Если попытка заканчивается на части $$$p$$$, то это означает, что она успешно проходит только через каждую часть $$$k$$$ для всех $$$1 \leq k \leq p-1$$$ и не достигает ни одной части $$$k$$$ для всех $$$p+1 \leq k \leq n$$$. Попытка, закончившаяся на части $$$p$$$, занимает $$$p$$$ секунд.

Известно, что Чанека улучшает ту часть, на которой она погибает, гораздо больше, чем все остальные. Известно также, что во время попытки Чанека не успевает потренироваться на тех частях, до которых она не дошла. Таким образом, эффект от попытки, которая заканчивается на части $$$p$$$, будет следующим:

  • Значение знакомства Чанеки с частью $$$p$$$ увеличивается на $$$2$$$.
  • Значение знакомства Чанеки с каждой частью $$$k$$$ для всех $$$1 \leq k \leq p-1$$$ увеличивается на $$$1$$$.
Имеется $$$q$$$ вопросов. В $$$j$$$-м вопросе Вам даются три целых числа $$$l_j$$$, $$$r_j$$$ и $$$x_j$$$. Затем требуется найти минимальное время (в секундах), которое потребуется Чанеке для того, чтобы значение знакомства с каждой частью $$$p$$$ ($$$l_j \leq p \leq r_j$$$) стало не меньше $$$x_j$$$.

Заметим, что каждый запрос является независимым, поэтому попытка, которую предпринимает Чанека в одном запросе, не влияет на значения знакомства в других запросах.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 3\cdot10^5$$$) — количество частей в Clubstep.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — значение знакомства Чанеки с каждой частью.

Третья строка содержит одно целое число $$$q$$$ ($$$1\leq q\leq3\cdot10^5$$$) — количество запросов.

В $$$j$$$-й из следующих $$$q$$$ строк содержатся три целых числа $$$l_j$$$, $$$r_j$$$ и $$$x_j$$$ ($$$1\leq l_j\leq r_j\leq n$$$; $$$1\leq x_j\leq10^9$$$) — описание $$$j$$$-го запроса.

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

Выведите $$$q$$$ целых чисел в отдельных строках. Число в $$$j$$$-й строке равняется минимальнму времени (в секундах), за которое Чанека может сделать так, чтобы значение знакомства для каждой части $$$p$$$ ($$$l_j \leq p \leq r_j$$$) было не менее $$$x_j$$$.

Пример
Входные данные
5
1 3 2 1 2
3
1 5 5
2 4 5
3 3 1
Выходные данные
15
11
0
Примечание

Для ответа на $$$1$$$-й вопрос можно поступить следующим образом:

  1. Сделать $$$1$$$ попытку, которая заканчивается на части $$$1$$$. Это занимает $$$1$$$ секунду. Значения знакомства становятся $$$[3, 3, 2, 1, 2]$$$.
  2. Выполнить $$$1$$$ попытку, которая заканчивается на части $$$4$$$. Это занимает $$$4$$$ секунды. Значения знакомства становятся $$$[4, 4, 3, 3, 2]$$$.
  3. Выполнить $$$2$$$ попытки, которые заканчиваются на части $$$5$$$. Это занимает $$$10$$$ секунд. Значения знакомства становятся $$$[6, 6, 5, 5, 6]$$$.

Общее время (в секундах) составляет $$$1+4+10=15$$$.

Для ответа на $$$2$$$-й вопрос можно поступить следующим образом:

  1. Сделать попытку $$$1$$$, которая заканчивается на части $$$3$$$. Это занимает $$$3$$$ секунды. Значения знакомства становятся $$$[2, 4, 4, 1, 2]$$$.
  2. Выполнить $$$2$$$ попытки, которые заканчиваются на части $$$4$$$. Это занимает $$$8$$$ секунд. Значения знакомства становятся $$$[4, 6, 6, 5, 2]$$$.

Общее время (в секундах) составляет $$$3+8=11$$$.