#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 25005;
int n, q, a[maxn];
int lpos[maxn], rpos[maxn];
int lpre[maxn], lnxt[maxn], rpre[maxn], rnxt[maxn];
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) {
		lpos[i] = rpos[i] = i;
		lpre[i] = rpre[i] = lnxt[i] = rnxt[i] = -1;
	}
	int res = 0;
	for(int i = 1, L, R; i <= q; i++) {
		scanf("%d%d", &L, &R);
		for(int j = L; j <= R; j++) {
			if(rpos[j] >= R) break;
			for(int k = rpos[j] + 1; k <= R; k++) {
				if(a[k] < a[j]) {
					if(rpre[j] == -1) {
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					} 
					else if(a[rpre[j]] < a[k]) {
						int x = rpre[j];
						if(lnxt[x] == j) res--;
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					}
				}
				else {
					if(rnxt[j] == -1) {
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
					else if(a[rnxt[j]] > a[k]) {
						int x = rnxt[j];
						if(lpre[x] == j) res--;
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
				}
			}
			rpos[j] = R;
		}
		for(int j = R; j >= L; j--) {
			if(lpos[j] <= L) break;
			for(int k = lpos[j] - 1; k >= L; k--) {
				if(a[k] < a[j]) {
					if(lpre[j] == -1) {
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
					else if(a[lpre[j]] < a[k]) {
						int x = lpre[j];
						if(rnxt[x] == j) res--;
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
				}
				else {
					if(lnxt[j] == -1) {
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
					else if(a[lnxt[j]] > a[k]) {
						int x = lnxt[j];
						if(rpre[x] == j) res--;
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
				}
			}
			lpos[j] = L;
		}
		printf("%d\n", res);
	}
	return 0;
}
### Prompt

Generate a CPP solution to the following problem:

Touko's favorite sequence of numbers is a permutation a_1, a_2, ..., a_n of 1, 2, ..., n, and she wants some collection of permutations that are similar to her favorite permutation.

She has a collection of q intervals of the form [l_i, r_i] with 1 ≤ l_i ≤ r_i ≤ n. To create permutations that are similar to her favorite permutation, she coined the following definition:

  * A permutation b_1, b_2, ..., b_n allows an interval [l', r'] to holds its shape if for any pair of integers (x, y) such that l' ≤ x < y ≤ r', we have b_x < b_y if and only if a_x < a_y. 
  * A permutation b_1, b_2, ..., b_n is k-similar if b allows all intervals [l_i, r_i] for all 1 ≤ i ≤ k to hold their shapes. 



Yuu wants to figure out all k-similar permutations for Touko, but it turns out this is a very hard task; instead, Yuu will encode the set of all k-similar permutations with directed acylic graphs (DAG). Yuu also coined the following definitions for herself:

  * A permutation b_1, b_2, ..., b_n satisfies a DAG G' if for all edge u → v in G', we must have b_u < b_v. 
  * A k-encoding is a DAG G_k on the set of vertices 1, 2, ..., n such that a permutation b_1, b_2, ..., b_n satisfies G_k if and only if b is k-similar. 



Since Yuu is free today, she wants to figure out the minimum number of edges among all k-encodings for each k from 1 to q.

Input

The first line contains two integers n and q (1 ≤ n ≤ 25 000, 1 ≤ q ≤ 100 000).

The second line contains n integers a_1, a_2, ..., a_n which form a permutation of 1, 2, ..., n.

The i-th of the following q lines contains two integers l_i and r_i. (1 ≤ l_i ≤ r_i ≤ n).

Output

Print q lines. The k-th of them should contain a single integer — The minimum number of edges among all k-encodings.

Examples

Input


4 3
2 4 1 3
1 3
2 4
1 4


Output


2
4
3


Input


8 4
3 7 4 8 1 5 2 6
3 6
1 6
3 8
1 8


Output


3
5
9
7


Input


10 10
10 5 1 2 7 3 9 4 6 8
2 2
4 5
6 8
4 10
4 4
2 7
2 2
7 8
3 7
2 10


Output


0
1
3
6
6
9
9
9
9
8

Note

For the first test case:

  * All 1-similar permutations must allow the interval [1, 3] to hold its shape. Therefore, the set of all 1-similar permutations is \{[3, 4, 2, 1], [3, 4, 1, 2], [2, 4, 1, 3], [2, 3, 1, 4]\}. The optimal encoding of these permutations is <image>
  * All 2-similar permutations must allow the intervals [1, 3] and [2, 4] to hold their shapes. Therefore, the set of all 2-similar permutations is \{[3, 4, 1, 2], [2, 4, 1, 3]\}. The optimal encoding of these permutations is <image>
  * All 3-similar permutations must allow the intervals [1, 3], [2, 4], and [1, 4] to hold their shapes. Therefore, the set of all 3-similar permutations only includes [2, 4, 1, 3]. The optimal encoding of this permutation is <image>

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 25005;
int n, q, a[maxn];
int lpos[maxn], rpos[maxn];
int lpre[maxn], lnxt[maxn], rpre[maxn], rnxt[maxn];
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) {
		lpos[i] = rpos[i] = i;
		lpre[i] = rpre[i] = lnxt[i] = rnxt[i] = -1;
	}
	int res = 0;
	for(int i = 1, L, R; i <= q; i++) {
		scanf("%d%d", &L, &R);
		for(int j = L; j <= R; j++) {
			if(rpos[j] >= R) break;
			for(int k = rpos[j] + 1; k <= R; k++) {
				if(a[k] < a[j]) {
					if(rpre[j] == -1) {
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					} 
					else if(a[rpre[j]] < a[k]) {
						int x = rpre[j];
						if(lnxt[x] == j) res--;
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					}
				}
				else {
					if(rnxt[j] == -1) {
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
					else if(a[rnxt[j]] > a[k]) {
						int x = rnxt[j];
						if(lpre[x] == j) res--;
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
				}
			}
			rpos[j] = R;
		}
		for(int j = R; j >= L; j--) {
			if(lpos[j] <= L) break;
			for(int k = lpos[j] - 1; k >= L; k--) {
				if(a[k] < a[j]) {
					if(lpre[j] == -1) {
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
					else if(a[lpre[j]] < a[k]) {
						int x = lpre[j];
						if(rnxt[x] == j) res--;
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
				}
				else {
					if(lnxt[j] == -1) {
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
					else if(a[lnxt[j]] > a[k]) {
						int x = lnxt[j];
						if(rpre[x] == j) res--;
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
				}
			}
			lpos[j] = L;
		}
		printf("%d\n", res);
	}
	return 0;
}
```