Problem

You are given a permutation A of length N.

There are Q queries. In each query, you are given L and R. Determine the number of subsequences B from the subarray A[L...R] such that |B| = max(B). |B| is the length of the array B.

Input

• N: Represents the length of the permutation A
• A: Represents N space-separated integers denoting the permutation elements
• Q: Represents the number of queries
• Queries: Represents Q ranges L, R given in a 2D array

Output

For each test case, print Q space-separated integers answer to each query modulo (10^9+7) in a new line.

Constraints

• 1 <= N <= 10^5
• 1 <= Q <= 10^5
• 1 <= L <= R <= N
• A is a permutation of length N, so all elements are unique

Subtle Requirements

• The problem requires counting subsequences where the length of the subsequence equals the maximum element in the subsequence.
• The answer should be given modulo (10^9+7).

Example 1

• N = 3
• A = [2,1,3]
• Q = 1
• Queries = [[2,3]]

The subarray from L = 2 to R = 3 is [1,3]. There is only one subsequence (1) that satisfies the given condition.

Example 2

• N = 4
• A = [2,3,1,4]
• Q = 2
• Queries = [[1,2],[2,3]]

The subarray from L = 1 to R = 2 is [2,3]. No subsequence satisfies the given condition.

The subarray from L = 2 to R = 3 is [3,1]. There is only one subsequence (1) that satisfies the given condition.