In one game there are N levels, and for each of them one can earn any integer number of points, including zero and negative values. Vadim can complete the i-th level for a_i points.

A progress is a consecutive sequence of levels such that the points strictly increase. For example, if the 2-nd level is completed for −4 points, the 3-rd — for 0 points, and the 4-th — for 3 points, then this sequence of levels and points is a progress.

The progressiveness of a level is the size of the largest progress, by number of levels, not by points, that contains this level. For example, if the levels are completed for [9, 4, 5, 6, 1] points, then the progressiveness of the 3-rd level is 3, since the progress [4, 5, 6] cannot be extended either to the left or to the right.

It is clear that all players are interested only in the total progressiveness of all levels. Vadim computed his own and was a little disappointed. He spent the next Q days changing his strategy. On each of these days, one of two things could happen:

After each day, Vadim computed the new total progressiveness. In total, he obtained Q+1 records. Your task is to restore all of them from the described strategy changes.

The first line contains an integer N — the number of levels in the game (2 ≤ N ≤ 10⁵).

The second line contains N integers a_i — the initial number of points Vadim gets for completing the i-th level (−10⁹ ≤ a_i ≤ 10⁹).

The third line contains an integer Q — the number of days with changes (1 ≤ Q ≤ 10⁵).

The following Q lines describe the changes in one of the following formats:

For each day, the inequalities 1 ≤ l_j ≤ r_j ≤ N and −10⁹ ≤ v_j ≤ 10⁹ hold.

Print Q+1 integers — the total progressiveness before the changes and after each of them.