Stone Painting Simulation

Bob has a row of \( n \) stones numbered from \(1\) to \( n \). Each stone \( i \) has an integer \( a_i \) written on it, and the numbers form a permutation of \( \{1,2,\ldots,n\} \). Two stones are considered adjacent if their indices differ by 1.

Bob performs exactly \( n \) operations as follows:

1. At step 1, he chooses any stone \( i \) (\(1\le i\le n\)) and paints it white.
2. For steps \(2\) to \( n \), he selects among the remaining black stones that have at least one already white neighbor. In this set, he chooses the stone \( j \) with the smallest value of \( a_j \) (if there are multiple candidates, the one with the smallest \( a_j \) is uniquely defined) and paints it white.

After \( n \) steps, all stones become white.

Alice gives Bob \( q \) queries. In each query, she provides two integers \( p \) and \( k \). For each query, Bob must determine in how many ways (i.e. by choosing the initial stone in step 1) the stone number \( p \) is painted white exactly at step \( k \).

Note: All formulas are written in LaTeX format. For example, the number of stones is denoted by \( n \) and the number on the \( i \)-th stone is \( a_i \).

inputFormat

The first line contains two integers \( n \) and \( q \) separated by a space.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) which form a permutation of \( \{1,2,\ldots,n\} \).

Then \( q \) lines follow, each containing two integers \( p_j \) and \( k_j \) representing a query.

outputFormat

For each query, output the number of initial choices such that the stone number \( p \) is painted white exactly at step \( k \). Each answer should be printed on a new line.

sample

3 2
2 3 1
1 1
3 3

1
1