В одной игре N уровней, за каждый из которых можно получать какое угодно целое количество очков (в том числе и нулевое, и отрицательное). Вадим умеет проходить i-й уровень на a_i очков.

Прогрессом считается набор уровней подряд, очки за которые строго увеличиваются. Например, если 2-й уровень пройден на −4 очка, 3-й — на 0 очков, а 4-й — на 3 очка, то такой набор уровней и очков — прогресс.

Прогрессивность уровня — размер наибольшего по количеству (не по очкам) прогресса, которому принадлежит уровень. Например, если уровни пройдены на [9, 4, 5, 6, 1] очков, то прогрессивность 3-го уровня равна 3, так как прогресс [4, 5, 6] нельзя увеличить ни влево, ни вправо.

Понятно, что всех игроков интересует лишь суммарная прогрессивность всех уровней. Вадим посчитал свою и немного разочаровался. Следующие Q дней он потратил на изменение своей стратегии. В каждый из дней могло произойти одно из двух:

После каждого дня Вадим считал новую суммарную прогрессивность. Всего у него получилось Q+1 записей. Ваша цель заключается в том, чтобы восстановить их все по описанным изменениям стратегии.

В первой строке даётся целое число N — количество уровней в игре (2 ≤ N ≤ 10⁵).

Во второй строке даются N целых чисел a_i — изначальное количество очков, которое получает Вадим за прохождение i-го уровня (−10⁹ ≤ a_i ≤ 10⁹).

В третьей строке даётся целое число Q — количество дней с изменениями (1 ≤ Q ≤ 10⁵).

В следующих Q строках описаны изменения в одном из двух форматов:

Для каждого дня верны неравенства 1 ≤ l_j ≤ r_j ≤ N и −10⁹ ≤ v_j ≤ 10⁹.

Выведите Q+1 целых чисел — суммарную прогрессивность до изменений и после каждого из них.