Let \(b_i\) be the number of strawberries on Piece \(i\). Then, we can express the request of Friend \(i\) as follows:

• if \(i < N\), \(b_i + b_{i+1} + \cdots + b_{i+N-1} \geq A_i\);
• if \(i \geq N\), \(b_i + b_{i+1} + \cdots + b_{2N-1} + b_0 + \cdots + b_{i-N-1} \geq A_i\).

We want to minimize the total number of strawberries \(b_0 + b_1 + \cdots + b_{2N-1}\) while satisfying these conditions.

Let \(X_{opt}\) be the minimum number of strawberries needed. Then, for any \(X \geq X_{opt}\), we can have exactly \(X\) strawberries on the whole cake, so let us do a binary search on the answer to turn the problem into a decision problem: can we have exactly \(X\) strawberries on the whole cake?

Conveniently, for a fixed total number of strawberries, the condition for \(i \geq N\), \(b_i + b_{i+1} + \cdots + b_{2N-1} + b_0 + \cdots + b_{i-N-1} \geq A_i\), is equivalent to \(b_{i-N} + b_{i-N+1} + \cdots + b_{i-1} \leq X - A_i\).

Additionally, let \(s_i = d_0 + d_1 + \cdots + d_{i-1}\). Then, the request of Friend \(i\) can be expressed as follows:

• if \(i < N\), \(s_{i+N} - s_i \geq A_i\);
• if \(i \geq N\), \(s_i - s_{i-N} \leq X - A_i\).

Thus, the problem is equivalent to determining whether it is possible to satisfy all of the following conditions, where \(L_i = A_i, R_i = X - A_{i+N}\):

• \(0 = s_0 \leq s_1 \leq \cdots \leq s_{2N} = X\);
• \(L_i \leq s_{i+N} - s_i \leq R_i\) for every \(i = 0, 1, \dots, N-1\).

Let us first consider the case the value of \(s_N\) is fixed to \(M\). We can solve this case as follows:

1. First, we have \(s_0 = 0, s_N = M\).
2. For each \(i = 1, 2, \dots, N-1\) in this order, do the following:
   • if \(L_i \leq s_{i+N-1} - s_{i-1} \leq R_i\), let \((s_i, s_{i+N}) = (s_{i-1}, s_{i+N-1})\);
   • if \(s_{i+N-1} - s_{i-1} < L_i\), let \((s_i, s_{i+N}) = (s_{i-1}, s_{i-1} + L_i)\);
   • if \(s_{i+N-1} - s_{i-1} > R_i\), let \((s_i, s_{i+N}) = (s_{i+N-1} - R_i, s_{i+N-1})\).
3. If we end up with both \(s_{N-1} \leq s_N\) and \(s_{2N-1} \leq X\), we have made a sequence satisfying the conditions. Otherwise, there is no sequence satisfying them.

We have no time to do this for all possible values of \(s_N\), but notice the following property:

Let \(f_1(a, b), f_2(a, b)\) be respectively the values of \(s_{N-1}, s_{2N-1}\) obtained in the greedy algorithm above when we first set \(s_0 = a, s_N = b\). If \(a \leq a', b \leq b'\), then \(f_1(a, b) \leq f_1(a', b')\) and \(f_2(a, b) \leq f_2(a', b')\) hold.

From this, the larger \(s_N\) is, the larger \(s_{2N-1}\) will be, so the condition \(s_{2N-1} \leq X\) will hold when \(s_N\) is not larger than some constant value (possibly \(-\infty\)).

Additionally, the larger \(s_N\) is, the smaller \(s_N - s_{N-1}\) will be, because if we hypothetically let \(s_0 = -M, s_N = 0\), the smaller \(M\) is, the larger \(s_{N-1}\) will be. Thus, the condition \(s_{N-1} \leq s_N\) will hold when \(s_N\) is not less than some constant value (possibly \(\infty\)).

Therefore, we can do a binary search to find the range of \(s_N\) where we can make a sequence, which solves the decision problem in \(O(N \log A)\) time, and the whole problem in \(O(N \log^2 A)\) time.

It is also possible to solve the decision problem in \(O(N)\) time, resulting in the total complexity of \(O(N \log A)\).

(Although it will not run in time, we note that it is possible to solve the decision problem using the Bellman-Ford algorithm in \(O(N^2)\) time by seeing it as a special case of a linear programming problem.)

Sample Implementations:

• C++: https://atcoder.jp/contests/arc117/submissions/21840539
• Java: https://atcoder.jp/contests/arc117/submissions/21840499
• PyPy3: https://atcoder.jp/contests/arc117/submissions/21839329