Butterfly and Telephone Poles (Hard)

Nabi is in charge of managing the utility poles in a new city. The wires are not connected yet, so Nabi must connect the wires between these poles. $N$ poles stand in a straight line, spaced $1$ apart, numbered $1$ through $N$ from left to right. The first pole is at position $1$, and initially the height of pole $i$ is $H_i$. On a coordinate plane, pole $i$ is the segment from $(i,0)$ to $(i,H_i)$.

A wire connects the tops of two poles by the shortest distance. If pole $i$ and pole $j$ are connected, the segment from $(i,H_i)$ to $(j,H_j)$ is drawn. The connection cost is the square of the wire length.

Nabi chooses the start pole $p$ and some poles including pole $p$, and connects them with wires. Sort the chosen poles by number as $S_1, S_2, \ldots, S_k$. Then pole $S_i$ is connected to pole $S_{i+1}$ for $1 \le i < k$.

Nabi must choose and connect the poles under these conditions.

• A wire must not cross a pole. However, a wire may meet pole $i$ at its top $(i,H_i)$.
• Moving left from $p$, the heights of the chosen poles are non-decreasing. Moving right from $p$, the heights of the chosen poles are also non-decreasing. In other words, if $S_t = p$, then $H_{S_1} \ge H_{S_2} \ge \cdots \ge H_{S_{t-1}} \ge H_p \le H_{S_{t+1}} \le H_{S_{t+2}} \le \cdots \le H_{S_k}$.
• Nabi wants the total wire length to be as large as possible. If several choices give the same maximum, Nabi chooses the one with the smallest total connection cost.

The city is still under construction, so the plan may change and pole heights may be updated. Junhyuk gives Nabi $Q$ tasks. Each task either changes the height of a pole, or gives a start pole and asks for the total connection cost.

The first line contains $N$ $(1 \le N \le 250\,000)$.

The second line contains integers $H_1, H_2, \ldots, H_N$ separated by spaces $(1 \le H_i \le 10^6)$.

The third line contains the number of tasks $Q$ $(1 \le Q \le 250\,000)$.

Each of the next $Q$ lines contains two integers $a$ and $b$.

• If $a$ is $0$, print the total connection cost when the start pole is $p = b$ $(1 \le b \le N)$.
• Otherwise, change the height of pole $a$ to $b$ $(1 \le b \le 10^6)$.

For each task with $a = 0$, print the total connection cost when $p = b$ on its own line.