CF739C Alyona and towers

Alyona 用一些小立方体搭建了 $n$ 座高塔，每个立方体的尺寸为 $1×1×1$。每座高塔是由若干个立方体垂直堆叠而成，且每座高塔至少包含一个立方体。这些高塔紧挨在一起，排成一行。 有时，Alyona 会选择一段连续的高塔，并在每座高塔的顶部额外叠加若干个立方体。具体来说，Alyona 选择区间 $l_i$ 到 $r_i$ 的高塔，并在它们的顶部各加上 $d_i$ 个立方体。 设当前各高塔的高度从左至右为 $a_1,a_2,\dots,a_n$。称区间 $a_l,a_{l+1},\dots,a_r$ 为一个“hill”（“山丘”），如果存在一个整数 $k$（$l\le k\le r$）满足 $a_la_r$。 每次操作后，Alyona 想知道所有“山丘”中宽度最大者的宽度。这里，“山丘”的宽度是高塔的数量，即 $r-l+1$。

第一行包含一个整数 $n$（$1\le n\le 3\times 10^5$），表示高塔的数量。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$），表示每座高塔当前的高度（立方体数）。 第三行包含一个整数 $m$（$1\le m\le 3\times 10^5$），表示操作次数。 接下来 $m$ 行，每行包含三个整数 $l_i, r_i, d_i$（$1\le l_i\le r_i\le n,\ 1\le d_i\le 10^9$），表示在第 $l_i$ 到第 $r_i$ 座高塔的顶部各放置 $d_i$ 个立方体。

输出 $m$ 行，第 $i$ 行输出第 $i$ 次操作后山丘的最大宽度。

第一个样例说明如下： 第一次操作，在第 1 到第 3 座高塔上各加 2 个立方体，结果高塔高度变为 $[7,7,7,5,5]$。此时最长的“山丘”为 $[7,5]$，宽度为 2。 第二次操作，在第 2 座高塔再加 1 个立方体，高度变为 $[7,8,7,5,5]$。最长“山丘”为 $[7,8,7,5]$，宽度为 4。 第三次操作，在第 4 座高塔再加 1 个立方体，高度变为 $[7,8,7,6,5]$。最长“山丘”为 $[7,8,7,6,5]$，宽度为 5。 由 ChatGPT 5 翻译