#P1485B. Replace and Keep Sorted
Replace and Keep Sorted
Description
Given a positive integer , two arrays are called -similar if:
- they are strictly increasing;
- they have the same length;
- all their elements are positive integers between and (inclusive);
- they differ in exactly one position.
You are given an integer , a strictly increasing array and queries. For each query, you are given two integers . Your task is to find how many arrays exist, such that is -similar to array .
The first line contains three integers , and (, ) — the length of array , the number of queries and number .
The second line contains integers (). This array is strictly increasing — .
Each of the following lines contains two integers , ().
Print lines. The -th of them should contain the answer to the -th query.
Input
The first line contains three integers , and (, ) — the length of array , the number of queries and number .
The second line contains integers (). This array is strictly increasing — .
Each of the following lines contains two integers , ().
Output
Print lines. The -th of them should contain the answer to the -th query.
Samples
Note
In the first example:
In the first query there are arrays that are -similar to : .
In the second query there are arrays that are -similar to : .