The answer to the query can be found as \(f(r _ i)-f(l _ i)\), if we can evaluate the following function:

• \(f(x)\coloneqq\) how many minutes did he sleep during the first \(x\) minutes since he started recording his sleeping log?

Since \(f(x)\) is a linear function within the range \(A _ i\leq x\leq A _ {i+1}\), we can find \(f(x)\) fast in the following way:

1. Precalculate \(f(A _ i)\ (1\leq i\leq N)\).
2. Find \(j\) such that \(A _ j\leq x\leq A _ {j+1}\).
3. Find \(f(x)\) from \(f(A _ j),f(A _ {j+1})\).

The values \(f(A _ i)\ (1\leq i\leq N)\) can be computed in a total of \(O(N)\) time in ascending order of \(i\).

The index \(j\) such that \(A _ j\leq x\leq A _ {j+1}\) can be found in an \(O(\log N)\) time with a binary search.

Computing \(f(x)=f(A _ j)+(x-A _ j)\dfrac{f(A _ {j+1})-f(A _ j)}{A _ {j+1}-A _ j}\) requires only a constant time.

Therefore, the problem has been solved in a total of \(O(N+Q\log N)\) time.
By pre-fetching and sorting the queries, one can also solve it in a total of \(O(N+Q\log Q)\) time.

The following is a sample code.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;
    vector<unsigned> A(N), fA(N);
    for (auto &&a : A)
        cin >> a;

    // fA[i] := how long did he sleep until time A[i]?
    for (unsigned i = 1; i < N; ++i)
        if (i % 2 == 0)
            fA[i] = fA[i - 1] + A[i] - A[i - 1];
        else
            fA[i] = fA[i - 1];

    unsigned Q;
    cin >> Q;

    // f(x) := how long did he sleep until time x?
    auto f{[&A, &fA](auto x) -> unsigned {
        const auto j = upper_bound(begin(A) + 1, end(A), x) - begin(A) - 1;
        return fA[j] + (fA[j + 1] - fA[j]) / (A[j + 1] - A[j]) * (x - A[j]);
    }};
    for (unsigned i = 0; i < Q; ++i) {
        unsigned l, r;
        cin >> l >> r;
        cout << f(r) - f(l) << endl;
    }

    return 0;
}