Longest Equal Even-Odd Subarray

You are given an array \(A\) of \(n\) integers. For a given range \([l, r]\) (0-indexed) in the array, your task is to determine the length of the longest contiguous subarray within that range that has an equal number of even and odd integers. In other words, for a subarray \(A[i..j]\) (where \(l \le i \le j \le r\)), if we denote the number of even integers by \(E\) and the number of odd integers by \(O\), the subarray is valid if \(E = O\) (i.e., \(E - O = 0\)). If no such subarray exists, return 0.

Input Format:

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array \(A\).
• The third line contains an integer \(q\), the number of queries.
• Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) (0-indexed) representing a query.

Output Format:

• For each query, output a single line containing the length of the longest contiguous subarray within the specified range that has equal numbers of even and odd integers.

Example:

Input:
8
1 2 3 4 5 6 7 8
3
0 7
1 4
2 6
Output:
8
4
4

</p>

In the first query, the entire array has 4 even and 4 odd numbers, making the longest valid subarray length 8.

inputFormat

The input is given from standard input and is structured as follows:

• An integer \(n\) denoting the number of elements in the array.
• A line of \(n\) space-separated integers representing the array.
• An integer \(q\) representing the number of queries.
• \(q\) lines each containing two space-separated integers \(l\) and \(r\), representing a query's inclusive range.

outputFormat

For each query, print a single line containing one integer - the length of the longest contiguous subarray within the given range [l, r] that has an equal number of even and odd numbers. If no such subarray exists, output 0.

## sample

8
1 2 3 4 5 6 7 8
1
0 7

8