题面描述

小智种了$n$朵花，这些花从左到右排成了一排，每朵花都有自己的美丽值$a_i$。除此之外，花朵之间的美丽值差距会带来总体的反差感，反差感越强，小智会觉得整体越美丽。

两朵相邻的花$i和i-1$之间的反差感定义为他们美丽值的差的平方，即$(a_i-a_{i-1})^2$

接下来小智获得了一些美丽之幻药，可以让花的美丽值改变

小智可以进行以下操作$q$次：

​ 使用幻药，使区间$[l,r]$的花的美丽值$a_l,a_{l+1}...a_{r-1},a_r$ 同时增加$w$

输入

第一行输入一个整数$n$，代表花的个数。$(1\leq n \leq 10^5)$

第二行输入$n$个整数,$a_1,a_2...a_{n-1},a_n$,代表第$i$朵花的美丽值。$(1 \leq a_i \leq 10^3)$

第三行输入一个整数$q$，代表小智的操作次数。$(1\leq q \leq 10^5)$

接下来的$q$行，每行包含三个整数:

​ $l$ $r$ $w$ ，代表，使用幻药，对$l,r$区间内的花的美丽值增加$w$。$(1\leq l \leq r \leq n,-10^2\leq w \leq 10^2)$

输出

输出$q$行整数：

对于每次操作输出一行整数，代表此时所有的花的美丽值与反差感之和。

样例输入 1

5
1 2 3 4 5
4
1 4 5
2 3 -3
3 5 3
1 5 -2

样例输出 1

54
66
90
80

测试数据