I. Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yam told Alter about the following problem:

You are given an array of $$$n$$$ elements, $$$a_1, a_1, \dots, a_n$$$. You can perform the following 2 operations any number of times in any order:

  1. Remove the last element of the array. This operation can only be performed if the array is nonempty after the operation.
  2. Add any number to the end of the array.

You want to minimize the number of operations of type (2) performed in order to turn the array into a permutation. We define this number to be the value of an array.

Now, Yam gives Alter $$$q$$$ queries, asking for the value of a subarray. Since Alter can only process one query at a time, he asks you to solve the problem.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The following line contains $$$n$$$ integers, the $$$i$$$-th of which is $$$a_i$$$ ($$$1\le a_i \le 10^9$$$).

The next $$$q$$$ lines contain two integers $$$l$$$, $$$r$$$, which describe the left and right endpoints (inclusive) of the queries ($$$1\le l \le r \le n$$$).

—

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

Tests $$$1-2$$$ satisfy $$$n, q\le 1000$$$.

Tests $$$3-8$$$ guarantee that all $$$a_i$$$ are distinct.

Tests $$$9-12$$$ satisfy no additional constraints.

Output

For each query, output a single integer — the value of the subarray.

Examples
Input
5 3
4 5 6 2 1
3 5
2 4
3 4
Output
3
3
4
Input
5 3
3 8 4 2 4
2 5
3 4
1 4
Output
5
2
2
Note

In the first sample test case:

The first query asks for the answer to the array $$$[6, 2, 1]$$$. One way to achieve the minimum number of type (2) operations is:

  1. Add the element $$$3$$$. The array is now $$$[6, 2, 1, 3]$$$
  2. Add the element $$$5$$$. The array is now $$$[6, 2, 1, 3, 5]$$$.
  3. Add the element $$$4$$$. The array is now $$$[6, 2, 1, 3, 5, 4]$$$.

The first sample test case satisfies the conditions of tests $$$3-8$$$.

—

Problem Idea: jay_jayjay

Problem Preparation: jay_jayjay

Occurrences: Advanced I