D. Pennant Hanging
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. G's students are hanging up pennants! There is a wall with $$$L$$$ slots, and has $$$N$$$ pennants hung on slots $$$1$$$ through $$$N$$$. The pennant in the $$$i$$$-th slot has rank $$$r_i$$$ (not necessarily distinct), and the pennants are ordered by rank, so $$$r_i\le r_{i+1}$$$ for $$$1\le i \lt N$$$. In one second, the students can either take a pennant off of a slot, or put a pennant of any rank onto the wall in any slot.

The students have put up all the pennants already, if they find $$$a$$$ extra pennants of rank $$$k$$$, then they must rearrange the pennants such that every pennant is on the wall, and the pennants are ordered by rank. It is guaranteed that this is always possible in finite time.

Mr. G has $$$q$$$ queries of $$$(a,k)$$$, and wants to find out the minimum time the students will take for each combination of $$$(a,k)$$$. Note that the pennants are not actually rearranged, that is, the queries are independent of each other.

note: the above image is not intended to be an accurate representation of the problem.

Input

The first line of input contains three integers $$$N$$$, $$$Q$$$, and $$$L$$$ ($$$1\le N, Q\le 2\cdot 10^5$$$, $$$N\le L\le 10^9$$$).

The following line contains $$$N$$$ integers $$$r_1, \dots, r_N$$$, ($$$1\le r_i\le N$$$). It is guaranteed that $$$r_i\le r_{i+1}$$$ for $$$1\le i \lt N$$$.

The following $$$q$$$ lines contain two integers $$$a$$$, $$$k$$$, which denote the number and rank of the newly found pennants for each query ($$$1\le a \le L-N$$$, $$$1\le k\le N$$$).

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-3$$$ satisfy $$$N, Q\le 200$$$.

Tests $$$4-20$$$ satisfy no additional constraints.

Output

Output $$$Q$$$ lines, the $$$i$$$-th line containing a single integer, the minimum time (in seconds) the students will take for the $$$i$$$-th query.

Example
Input
5 5 10
1 3 4 5 5
2 1
5 4
4 2
4 3
5 1
Output
10
9
12
10
13
Note

In the first query, it is optimal for the students to take off the last 4 pennants, and then put up the 6 pennants (including the new ones) in order.

—

Problem Idea: jay_jayjay

Problem Preparation: jay_jayjay

Occurrences: Novice I / Advanced D