We use the second approach of this editorial for problem E. (We assume that there are an infinite number of mochi’s of an infinite size after the sequence, and consider the smallest index of a mochi for the bottom to pair the first \(K\) mochi’s as the top.)

Let \(B _ i\coloneqq\) the smallest index \((1\leq i\leq N)\) eligible for the bottom mochi when using the \(i\)-th mochi as the top.

Then, the answer for \((L,R)\) is the maximum \(K\) with \(\displaystyle L+K-1+\max\left\lbrace\max _ {L\leq i\lt L+K}\lbrace B _ i-i\rbrace,K\right\rbrace\leq R\). Since the left hand side is monotonic with respect to \(K\), the problem can be solved by managing \(B _ i-i\) with a segment tree and performing binary search on it.

The time complexity is \(O(N+Q\log N)\).

The following is sample code. We use the algorithm for binary searching on a segment tree, leading to the overall time complexity of \(O(N+Q\log N)\).

#include <iostream>
#include <vector>
#include <atcoder/segtree>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;

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

    // A segment tree that maintains (the length of the segment, the maximum B[i] - i)
    using value_type = pair<unsigned, unsigned>;
    atcoder::segtree<value_type, [](const auto& lhs, const auto& rhs) {
        const auto& [left_length, left_distance_max]{lhs};
        const auto& [right_length, right_distance_max]{rhs};
        return value_type{left_length + right_length, max(left_distance_max, right_distance_max)};
    }, [] { return value_type{}; }> segment_tree{
        [N](const auto& seq) {
            vector<value_type> result(N);
            // Find B[i] in a total of Θ(N) time
            for (unsigned i{}, j{}; i < N; ++i) {
                while (j < N && seq[i] * 2 > seq[j]) ++j;
                result[i] = {1, j - i};
            }
            return result;
        }(A)
    };

    unsigned Q;
    cin >> Q;

    for (unsigned i{}; i < Q; ++i) {
        unsigned L, R;
        cin >> L >> R;
        --L;
        // Find the maximum [L, L+K) for which the right end does not exceed R
        cout << segment_tree.max_right(L, [L, R](const auto& itv) {
            const auto& [length, distance]{itv};
            return L + length + max(distance, length) <= R;
        }) - L << endl;
    }

    return 0;
}