Problem

You are given a code for the following problem statement in the findSubsequence function. However, the solution fails the test cases because there are bugs in the code. Your task is to find and fix all the bugs so that it passes all the test cases.

Statement

You are given the following:

• N: An integer
• A: An array of integers where the value of elements is either 1 or -1.

A query consists of two integers, L and R. For a query you have to find the maximum possible length of a subsequence chosen from subarray A[L..R], which follows the given condition:

• If the length of subsequence is K, say subsequence is b1, b2, ..., bK, then.
• All prefix sums of the subsequence are non-negative.
• The sum of all the elements in the subsequence is 0.

If no such subsequence exists, you should output 0.

Task

You have to process Q-independent queries, where in each query, you have to determine the length of the maximum possible subsequence.

Notes

• 1-based Indexing is followed
• A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements

Example

Assumptions

• A = [1, 1, 1, -1, -1, -1]
• query = [[1, 6], [4,6]]

Approach For first query:

• L = 1, R = 6
• The subsequence [1, 1, 1, -1, -1, -1] satisfies the above conditions.
• Hence, the answer is 6.

For the second query:

• L = 4, R = 6.
• There does not exist any such subsequence.
• Hence, the answer is 0.