During the process, \(A_i\leq 0\) never holds. Thus, there exists a minimum possible value of \(\sum A_i\) after the process.

Let us take one sequence with this minimum sum and call it \(B\). Also, in this editorial, let \(A(x), B(x)\) denote their \(x\)-th terms \(A_x, B_x\).

For convenience, let \(A(x) = B(x) = \infty\) for \(x < 1\) or \(N < x\).

---

◆ The convexity of \(B\)

From the fact that an operation with \((i,j,k) = (x-1,x,x+1)\) does not reduce \(\sum_{x=1}^N B(x)\), we have \(2B(x) \leq B(x-1) + B(x+1)\) for any \(x\).

A function \(B\colon \Z\longrightarrow \mathbb{R}\) with this property is called a discrete convex function.

---

◆ The minimum of \(B\)

In the process of obtaining \(B\) from \(A\), we can assume that no operation is done to increase a term. That is, we have \(\min_{x\in \mathbb{Z}} B(x) = \min_{x\in \mathbb{Z}} A(x)\).

By generalizing this observation, we can show the following: for any \(p\in \mathbb{Z}\), \(\min_{x\in \mathbb{Z}} (B(x) - px) = \min_{x\in \mathbb{Z}} (A(x) - px).\)

---

◆ Determining \(B\)

Let \(a_p := \min_{x\in \mathbb{Z}} (A(x) - px)\).

From the aformentioned properties:

1. \(B\) is convex, that is, \(2B(x) \leq B(x-1) + B(x+1)\)
2. \(\min_{x\in \mathbb{Z}} (B(x) -px) = a_p\)

we can uniquely determine \(B\). Actually, we can prove that:

\(B(x) = \max_{p\in \mathbb{Z}}(px + a_p).\)

Proof that \(B(x) \geq \max_{p\in \mathbb{Z}}(px + a_p)\)

It is enough to fix \(x\) and show that \(B(x)\geq px + a_p\) for any \(p\in\mathbb{Z}\), which is obvious from the property 2.

Proof that \(B(x) \leq \max_{p\in \mathbb{Z}}(px + a_p)\)

It is enough to fix \(x\) and give one \(p\) such that \(B(x) \leq px+a_p\). From the convexity of \(B\), there is \(p\in \mathbb{Z}\) such that \(B(x)-B(x-1)\leq p\leq B(x+1)-B(x)\), for which \(B(x) - px = \min_{y\in \mathbb{Z}}(B(y) - py)\). Since the right side was equal to \(a_p\), we have \(B(x) - px = a_p\), which verifies the existence of \(p\) such that \(B(x) \leq px + a_p\).

---

Eventually, it has turned out that the optimal solution \(B\) is determined as follows.

• Let \(a_p = \min_{x\in \mathbb{Z}}(A(x) - px)\).
• We have \(B(x) = \max_{p\in \mathbb{Z}}(px + a_p)\).

For each \(p\), the \(x\) such that \(a_p = A(x) - px\) lies somewhere along the lower convex envelope of \(A\). By enumerating the points on the lower convex envelope, for each \(p\) we can find one \(x\) such that \(a_p = A(x) - px\). Let us write this \(x\) as \(x_p\).

For \(x_p\leq x\leq x_{p+1}\), we have \(B(x) = \max(px+a_p, (p+1)x + a_{p+1})\). This is because:

• if \(q \leq p\), we have \(qx_p+a_q\leq px_p + a_p\), from which \(qx_p + a_q\leq px_p+a_p\) holds;
• if \(q \geq p+1\), we have \(qx_{p+1}+a_q\leq qx_{p+1} + a_{p+1}\), from which \(qx + a_q\leq (p+1)x_{p+1}+a_{p+1}\) holds.

This formula allows us to compute \(B(x)\) such that \(x_p\leq x\leq x_{p+1}\), enabling us to find all \(B(x)\).

Proper implementation of the above solves the problem in \(O(N)\) time.

---