Problem Specification

Given an array of integers (A) with length (n), the goal is to determine the maximum length of a contiguous subsequence that can satisfy a specific threshold constraint. For each query, a value (k) is provided. A segment is valid if its elements can be redistributed using allowed operations such that every element in the segment eventually becomes at least (k).

The permitted operation allows transferring value between adjacent indices: decrementing an element (> k) by 1 and incrementing a neighbor by 1. This preserves the total sum of the selected subsegment.

Mathematical Transformation

Since the total sum remains invariant under the defined operasion, a subarray from index (L) to (R) satisfies the condition if and only if: [ \sum_{x=L}^{R} A_x \ge (R - L + 1) \times k \ ]\n By rearranging the inequality: [ \sum_{x=L}^{R} (A_x - k) \ge 0 \ ]

We define a transformed sequence (B) where (B_i = A_i - k). Let (P) denote the prefix sum array of (B), with (P_0 = 0). The condition for the subarray ([L, R]) transforms to finding endices (i) (representing (L-1)) and (j) (representing (R)) such that: [ P_j \ge P_i \ ]\n To maximize the length (j - i), we must identify pairs satisfying this inequality where (i < j).

Algorithmic Approach

This problem can be efficiently solved using a monotonic stack combined with a two-pass strategy.

Pass 1: Stack Initialization

Iterate through the array from left to right. Maintain a stack that stores indices corresponding to potential starting points (prefix sums). To maximize future lengths, we want to keep indices with smaller prefix sums deeper in the potential candidate set. However, standard implementation logic suggests maintaining indices where the prefix sum values are strictly decreasing as you move up the stack. This ensures that for any future index (j), if it satisfies (P_j \ge P_{top}), the top element represents a valid start point with the maximum possible distance from the current index among those currently in consideration.

Additionally, check if the current prefix sum itself is non-negative. If (P_j \ge 0), then the subarray from index 1 to (j) is valid, update the global maximum length accordingly.

Pass 2: Solution Verification

Iterate backwards from (n) down to (1), treating the current index as the right endpoint (R). While the stack is not empty and the current prefix sum satisfies (P_R \ge P_{stack.top()}), calculate the length (R - stack.top()), update the result, and pop the stack. Since we are iterating (R) downwards, removing these indices prevents them from being reused for shorter segments with larger left boundaries unnecessarily, while confirming they form valid long segments for the current maximal right endpoints.

Implementation

The following C++ solution demonstrates this approach using std::vector and std::stack.

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

using namespace std;

const int MAX_SIZE = 1000005;
long long prefix_sums[MAX_SIZE];
int values[MAX_SIZE];

void solve() {
    int n, q;
    if (!(cin >> n >> q)) return;

    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
    }

    while (q--) {
        int k;
        cin >> k;

        // Compute transformed prefix sums
        // B[i] = A[i] - k
        prefix_sums[0] = 0;
        for (int i = 1; i <= n; ++i) {
            prefix_sums[i] = prefix_sums[i - 1] + (values[i] - k);
        }

        stack<int> candidates;
        int max_length = 0;

        // Forward pass: Initialize stack
        for (int i = 1; i <= n; ++i) {
            // Check if entire prefix [1..i] is valid
            if (prefix_sums[i] >= 0) {
                max_length = max(max_length, i);
            }

            // Push index if prefix sum is smaller than current top
            // Maintains decreasing order of prefix sums in stack
            if (candidates.empty() || prefix_sums[i] < prefix_sums[candidates.top()]) {
                candidates.push(i);
            }
        }

        // Backward pass: Calculate maximum lengths
        for (int j = n; j >= 1; --j) {
            while (!candidates.empty() && prefix_sums[j] >= prefix_sums[candidates.top()]) {
                max_length = max(max_length, j - candidates.top());
                candidates.pop();
            }
        }

        cout << max_length << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Analysis of Edge Cases

Simple binary search approaches on the answerr size may fail. Consider a scenario where distributing values evenly across almost the entire array results in a total sum slightly less than required for full inclusion. Algorithms that greedily assume partial inclusion works might incorrectly verify segments. A rigorous check of cumulative sums across the full range, rather than heuristic splits, is necessary to handle cases like uniform distributions that barely miss or meet thresholds.