The problem statement is straightforward.

You are given an array A of n integers. Each integer element belongs to the set: {1, 2, 3}.
We define a subsequence as follows:
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For example: For a sequence : {1, 2, 3, 4, 5}
{1, 2}, {2, 3, 5}, {2, 5} are some subsequences but {2, 1}, {4, 2} are not.

You will be given q queries. Each query will be of the form l r.
You have to answer the maximum length of non-decreasing subsequence from l to r.

INPUT FORMAT
The first line of input contains an integer n, the number of elements in the array A.
The next line contains n elements of the array A separated by spaces.

The next line contain q, the number of queries.

Next q lines contain two space-separated integers l r.

OUTPUT FORMAT
For each query print a single line denoting the length of maximum 1,2,3 subsequence in array A between l to r (inclusive).

CONSTRAINTS
 
1 <= n, q<= 200000
1<=A[i]<=3

1<=l<=r<=n