Score : 800 points
There are N points on a number line, i-th of which is placed on coordinate X_i. These points are numbered in the increasing order of coordinates. In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds. In addition to that, an integer K is given.
Process Q queries.
In the i-th query, two integers L_i and R_i are given. Here, a set s of points is said to be a good set if it satisfies all of the following conditions. Note that the definition of good sets varies over queries.
For each query, find the size of the union of all good sets.
Input is given from Standard Input in the following format:
N K X_1 X_2 \cdots X_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
For each query, print the size of the union of all good sets in a line.
5 3 1 2 4 7 8 2 1 5 1 2
4 2
In the first query, you can have at most 3 points in a good set. There exist two good sets: \{1,4,7\} and \{1,4,8\}. Therefore, the size of the union of all good sets is |\{1,4,7,8\}|=4.
In the second query, you can have at most 1 point in a good set. There exist two good sets: \{1\} and \{2\}. Therefore, the size of the union of all good sets is |\{1,2\}|=2.
15 220492538 4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194 5 6 14 1 8 1 13 7 12 4 12
4 6 11 2 3