A. Neq Array
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a constraint array $$$A$$$ of length $$$N$$$, we generate a new integer array $$$B$$$ of length $$$N$$$ satisfying the following conditions:

  • All elements of $$$B$$$ are positive, i.e. $$$B_i \gt 0$$$
  • $$$B$$$ is non-decreasing, i.e. $$$B_1 \le B_2 \le B_3 \le .... \le B_N$$$.
  • $$$B_i \ne A_i$$$ for each $$$1 \le i \le N$$$
  • The last element of $$$B$$$, i.e. $$$B_N$$$ here is minimum possible.

Let $$$f(A)$$$ denote the minimum possible value of the last element of $$$B$$$ for a valid array $$$B$$$.

You will be given queries $$$L$$$ and $$$R$$$, and you need to answer $$$f(A[L, R])$$$ where $$$A[L, R]$$$ denotes the subarray $$$[A_L, A_{L + 1}, ..., A_R]$$$. That is, you need to answer the minimum value of the last element of $$$B$$$ possible if only the $$$L$$$-th to the $$$R$$$-th indices of $$$A$$$ were present.

There are multiple test cases in each file, and thus you will be given an input parameter $$$T$$$, denoting that you have to solve $$$T$$$ test cases.

Input

The first line of input contains $$$T$$$ - the number of test cases.

The first line of each test case contains $$$N$$$ and $$$Q$$$ - the size of the array $$$A$$$ and the number of queries respectively.

The second line of each test case contains $$$N$$$ integers - $$$A_1, A_2, ..., A_N$$$

The $$$j$$$-th of the next $$$Q$$$ lines contains $$$L_j$$$ and $$$R_j$$$ - the parameters of the $$$j$$$-th query.

Output

For each test case, output $$$Q$$$ integers on a single line, $$$f(A[L_j, R_j])$$$ for each query.

Scoring

Constraints

It is guaranteed that

  • $$$1 \le T \le 10^4$$$
  • $$$1 \le N, Q \le 2 \cdot 10^5$$$
  • $$$1 \le A_i \le N$$$
  • $$$1 \le L_j \le R_j \le N$$$
  • The sum of $$$N$$$ and the sum of $$$Q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$

Subtasks

The special constraint whole array means that $$$Q = 1, L_1 = 1, R_1 = N$$$, i.e. there is only one query which covers the whole array.

  • Subtask 1 (4 points) : $$$N = 2$$$ and whole array
  • Subtask 2 (15 points) : $$$N \le 1000$$$, whole array, and the sum of $$$N$$$ over all test cases does not exceed $$$1000$$$
  • Subtask 3 (8 points) : whole array
  • Subtask 4 (18 points) : $$$A_i \le 100$$$
  • Subtask 5 (12 points) : $$$|A_i - A_{i - 1}| \le 1$$$
  • Subtask 6 (20 points) : $$$R_j = N$$$ for all queries
  • Subtask 7 (23 points) : No additional constraints
Example
Input
3
2 1
2 1
1 2
4 2
1 2 3 4
1 4
2 4
6 5
2 1 1 3 2 1
1 6
2 5
4 6
3 3
5 5
Output
2
5 1
3 3 2 2 1
Note

Test Case 1 : This is a query on the whole array. $$$A = [2, 1]$$$ and we choose $$$B = [1, 2]$$$ which satisfies all conditions, while minimizing the last element value of $$$2$$$. It can be proven it is impossible to achieve a smaller value.

Test Case 2 : In the first query, the query is again of the whole array, $$$A = [1, 2, 3, 4]$$$ and we choose $$$B = [5, 5, 5, 5]$$$ which satisfies all conditions and minimizes the last element value of $$$5$$$.

In the second query, we work with the subarray $$$A = [2, 3, 4]$$$ instead, and we can choose $$$B = [1, 1, 1]$$$ here.