Let \(f(x)\) be the answer when we change to \(L = 0, R = x\). Then the answer to this problem can be expressed as \(f(R) - f(L - 1)\). Therefore, it suffices to find what value \(f(x)\) takes.

For \(2N\) operations, we define a sequence of pairs of length \(2N\): \(((a_1, b_1), \dots, (a_{2N}, b_{2N}))\) as follows:

• \(a_i\) is the number of times action 1 has been performed up to the \(i\)-th operation, and \(b_i\) is the number of times action 2 has been performed up to the \(i\)-th operation.

Then, the following holds for the final value of \(C\):

• \(\displaystyle C = \max_{1\leq i\leq 2N}\left(\sum_{s = 1}^{a_{i}}A_{s} - \sum_{t = 1}^{b_{i}}B_{t}\right) - \left(\sum A - \sum B\right)\)

Therefore, only when \(C\leq x\), the following holds for any integer \(1\leq i\leq 2N\):

• \(\left(\sum_{s = 1}^{a_{i}}A_{s} - \sum_{t = 1}^{b_{i}}B_{t}\right) \leq \left(\sum A - \sum B\right) + x\)

In addition to the above condition, the number of operation sequences where \(a_i \geq b_i\) holds for any integer \(1\leq i\leq 2N\) can be found using dynamic programming with time complexity \(O(N^2)\).

Therefore, under the constraints of this problem, we can find \(f(x)\) sufficiently fast, so we can also find the solution to this problem sufficiently fast.

Implementation Examples

C++ Implementation Example

PyPy Implementation Example

Supplement

Also, considering that this can be reduced to a certain problem on yosupo judge, it is also possible to find \(f(x)\) in \(O(N\log^{2}(N))\).