Consider a sequence \(d=(d_0,d_1,\dots,d_{N})\) defined as:

• \(d_0=A_1\),
• \(d_i=A_{i+1}-A_i\ (1\leq i \leq N-1)\),
• \(d_N=-A_N\).

The original problem can be rephrased using this differential array \(d\) as follows:

• You are given an array \(d\).
• You may perform the following operation any number of times: add \(1\) to \(d_{L_i-1}\) and subtract \(1\) from \(d_{R_i}\).
• Determine if one can make \(d_i \geq 0\) for all \(i\) between \(0\) and \(N-1\) (inclusive), and if it is possible, find the minimum number of operations required. (Note that \(d_N\) is allowed to become negative.)

More intuitively,

• There are \((N+1)\) boxes \(0,1,\dots,N\) with balls.
• For \(i\ (0 \leq i \leq N-1)\) with \(d_i > 0\), box \(i\) has \(d_i\) redundant balls.
• For \(i\ (0 \leq i \leq N-1)\) with \(d_i < 0\), box \(i\) wants \(d_i\) more balls.
• Box \(N\) has an infinite number of redundant balls.
• In one operation, one can choose any \(i\) and move one ball from box \(R_i\) to box \(L_i-1\).
• We want to fulfill all demands of balls by moving redundant balls with the minimum number of operations.

This can be formulated as a minimum-cost flow problem. Specifically, construct a graph \(G\) as follows:

• \(G\) has \((N+1)\) vertices \(0,1,\dots,N\), and two more vertices \(S\) and \(T\).
• \(G\) has the following edges:
  • For each \(i\ (0 \leq i \leq N-1)\) with \(d_i > 0\), an edge from \(S\) to \(i\) of capacity \(d_i\) and cost \(0\).
  • For each \(i\ (0 \leq i \leq N-1)\) with \(d_i < 0\), an edge from \(i\) to \(T\) of capacity \(-d_i\) and cost \(0\).
  • An edge from \(S\) to \(N\) of capacity \(\infty\) and cost \(0\).
  • For each \(i\ (1\leq i\leq M)\), an edge from \(R_i\) to \(L_i-1\) with capacity \(\infty\) and cost \(1\).

Let \(K=\displaystyle \sum_{i=0}^{N-1} \max(-d_i, 0)\) (which equals the sum of capacity of the edges pointing to \(T\) on \(G\)). If the maximum capacity from \(S\) to \(T\) on the graph \(G\) is less than \(K\), then the answer is \(-1\); otherwise, the answer is the cost of the minimum-cost maximum flow from \(S\) to \(T\).

The computational complexity is \(O(N(\max A_i)(N+M)\log(N+M))\).

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/mincostflow>

using namespace std;
using namespace atcoder;

const int inf = 1 << 30;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    mcf_graph<int, int> mcf(n + 3);
    int s = n + 1, t = s + 1;
    int req = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int dif = a[i] - (i ? a[i - 1] : 0);
        if (dif >= 0) {
            mcf.add_edge(s, i, dif, 0);
        } else {
            mcf.add_edge(i, t, -dif, 0);
            req += -dif;
        }
    }
    mcf.add_edge(s, n, inf, 0);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        --l;
        mcf.add_edge(r, l, inf, 1);
    }
    auto [flow, cost] = mcf.flow(s, t);
    if (flow < req) cout << -1 << endl;
    else cout << cost << endl;
}