M. Сумма превышений

Дан массив из $n$ чисел. Ответьте на $q$ запросов $(l, r, t)$: чему равна сумма

Иначе говоря, сколько всего надо снять с элементов отрезка, чтобы ни один не превышал $t$.

В первой строке — число $n$ ($1 \le n \le 10^5$). Во второй — $n$ чисел ($1 \le a_i \le 10^9$). В третьей — число $q$ ($1 \le q \le 10^5$). В следующих $q$ строках — тройки $l$, $r$, $t$ ($1 \le l \le r \le n$, $1 \le t \le 10^9$).

На каждый запрос выведите искомую сумму.