#include <bits/stdc++.h>
using namespace std;
const int N = 25005;
const int Q = 100005;
const int B = 80;
int n, q, a[N], pos[N], ql[Q], qr[Q], idx[Q], ans[Q], bit[N];
vector<int> vl[N], vr[N], sl[N], sr[N], tl[N], tr[N];
vector<pair<int, int*> > buck[N];
vector<pair<int, int> > buckq[N];
inline void add(int i, int x) {
	while (i <= n) {
		bit[i] = min(bit[i], x);
		i += i & -i;
	}
}
inline int qry(int i) {
	int ret = q + 1;
	while (i > 0) {
		ret = min(ret, bit[i]);
		i -= i & -i;
	}
	return ret;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	for (int i = 1; i <= q; i++) {
		scanf("%d%d", &ql[i], &qr[i]);
		idx[i] = i;
		buckq[qr[i]].push_back(make_pair(ql[i], i));
	}
	sort(idx + 1, idx + 1 + q, [](int i, int j) {
		return (ql[i] - 1) / B != (ql[j] - 1) / B ? ql[i] < ql[j] : qr[i] < qr[j];
	});
	set<int> st;
	set<pair<int, int> > cur;
	function<void(int)> Ins = [&](int x) {
		auto it = st.insert(x).first;
		if (it != st.begin()) cur.insert(make_pair(*prev(it), x));
		if (next(it) != st.end()) cur.insert(make_pair(x, *next(it)));
		if (it != st.begin() && next(it) != st.end()) cur.erase(make_pair(*prev(it), *next(it)));
	};
	function<void(int)> Del = [&](int x) {
		auto it = st.find(x);
		if (it != st.begin()) cur.erase(make_pair(*prev(it), x));
		if (next(it) != st.end()) cur.erase(make_pair(x, *next(it)));
		if (it != st.begin() && next(it) != st.end()) cur.insert(make_pair(*prev(it), *next(it)));
		st.erase(it);
	};
	for (int _ = 1, curl = 1, curr = 0; _ <= q; _++) {
		int i = idx[_];
		while (curr < qr[i]) Ins(a[++curr]);
		while (curl > ql[i]) Ins(a[--curl]);
		while (curr > qr[i]) Del(a[curr--]);
		while (curl < ql[i]) Del(a[curl++]);
		for (auto &P : cur) {
			int i = pos[P.first], j = pos[P.second];
			if (i < j) vr[i].push_back(j);
			else vl[i].push_back(j);
		}
		cur.clear();
	}
	vector<pair<int, int> > ev;
	for (int i = 1; i <= n; i++) {
		sort(vl[i].begin(), vl[i].end());
		vl[i].resize(unique(vl[i].begin(), vl[i].end()) - vl[i].begin());
		reverse(vl[i].begin(), vl[i].end());
		sort(vr[i].begin(), vr[i].end());
		vr[i].resize(unique(vr[i].begin(), vr[i].end()) - vr[i].begin());
		sl[i].resize(vl[i].size());
		tl[i].resize(vl[i].size());
		sr[i].resize(vr[i].size());
		tr[i].resize(vr[i].size());
		for (int j = 0, k = 0; j < (int)vl[i].size(); j++) {
			buck[i].push_back(make_pair(vl[i][j], &sl[i][j]));
			while (k < (int)vr[i].size() && a[vl[i][j]] < a[vr[i][k]]) k++;
			if (k < (int)vr[i].size()) {
				buck[vr[i][k]].push_back(make_pair(vl[i][j], &tl[i][j]));
			} else {
				tl[i][j] = q + 1;
			}
		}
		for (int j = 0, k = 0; j < (int)vr[i].size(); j++) {
			buck[vr[i][j]].push_back(make_pair(i, &sr[i][j]));
			while (k < (int)vl[i].size() && a[vr[i][j]] < a[vl[i][k]]) k++;
			if (k < (int)vl[i].size()) {
				buck[vr[i][j]].push_back(make_pair(vl[i][k], &tr[i][j]));
			} else {
				tr[i][j] = q + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) bit[i] = q + 1;
	for (int i = n; i >= 1; i--) {
		for (auto &P : buckq[i]) {
			add(P.first, P.second);
		}
		for (auto &P : buck[i]) {
			*P.second = qry(P.first);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (int)vl[i].size(); j++) {
			int L = sl[i][j], R = min(j < (int)vl[i].size() - 1 ? sl[i][j + 1] : q + 1, tl[i][j]);
			if (L < R) ans[L]++, ans[R]--;
		}
		for (int j = 0; j < (int)vr[i].size(); j++) {
			int L = sr[i][j], R = min(j < (int)vr[i].size() - 1 ? sr[i][j + 1] : q + 1, tr[i][j]);
			if (L < R) ans[L]++, ans[R]--;
		}
	}
	for (int i = 1; i <= q; i++) ans[i] += ans[i - 1];
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}
### Prompt

Create a solution in cpp for 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;
const int N = 25005;
const int Q = 100005;
const int B = 80;
int n, q, a[N], pos[N], ql[Q], qr[Q], idx[Q], ans[Q], bit[N];
vector<int> vl[N], vr[N], sl[N], sr[N], tl[N], tr[N];
vector<pair<int, int*> > buck[N];
vector<pair<int, int> > buckq[N];
inline void add(int i, int x) {
	while (i <= n) {
		bit[i] = min(bit[i], x);
		i += i & -i;
	}
}
inline int qry(int i) {
	int ret = q + 1;
	while (i > 0) {
		ret = min(ret, bit[i]);
		i -= i & -i;
	}
	return ret;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	for (int i = 1; i <= q; i++) {
		scanf("%d%d", &ql[i], &qr[i]);
		idx[i] = i;
		buckq[qr[i]].push_back(make_pair(ql[i], i));
	}
	sort(idx + 1, idx + 1 + q, [](int i, int j) {
		return (ql[i] - 1) / B != (ql[j] - 1) / B ? ql[i] < ql[j] : qr[i] < qr[j];
	});
	set<int> st;
	set<pair<int, int> > cur;
	function<void(int)> Ins = [&](int x) {
		auto it = st.insert(x).first;
		if (it != st.begin()) cur.insert(make_pair(*prev(it), x));
		if (next(it) != st.end()) cur.insert(make_pair(x, *next(it)));
		if (it != st.begin() && next(it) != st.end()) cur.erase(make_pair(*prev(it), *next(it)));
	};
	function<void(int)> Del = [&](int x) {
		auto it = st.find(x);
		if (it != st.begin()) cur.erase(make_pair(*prev(it), x));
		if (next(it) != st.end()) cur.erase(make_pair(x, *next(it)));
		if (it != st.begin() && next(it) != st.end()) cur.insert(make_pair(*prev(it), *next(it)));
		st.erase(it);
	};
	for (int _ = 1, curl = 1, curr = 0; _ <= q; _++) {
		int i = idx[_];
		while (curr < qr[i]) Ins(a[++curr]);
		while (curl > ql[i]) Ins(a[--curl]);
		while (curr > qr[i]) Del(a[curr--]);
		while (curl < ql[i]) Del(a[curl++]);
		for (auto &P : cur) {
			int i = pos[P.first], j = pos[P.second];
			if (i < j) vr[i].push_back(j);
			else vl[i].push_back(j);
		}
		cur.clear();
	}
	vector<pair<int, int> > ev;
	for (int i = 1; i <= n; i++) {
		sort(vl[i].begin(), vl[i].end());
		vl[i].resize(unique(vl[i].begin(), vl[i].end()) - vl[i].begin());
		reverse(vl[i].begin(), vl[i].end());
		sort(vr[i].begin(), vr[i].end());
		vr[i].resize(unique(vr[i].begin(), vr[i].end()) - vr[i].begin());
		sl[i].resize(vl[i].size());
		tl[i].resize(vl[i].size());
		sr[i].resize(vr[i].size());
		tr[i].resize(vr[i].size());
		for (int j = 0, k = 0; j < (int)vl[i].size(); j++) {
			buck[i].push_back(make_pair(vl[i][j], &sl[i][j]));
			while (k < (int)vr[i].size() && a[vl[i][j]] < a[vr[i][k]]) k++;
			if (k < (int)vr[i].size()) {
				buck[vr[i][k]].push_back(make_pair(vl[i][j], &tl[i][j]));
			} else {
				tl[i][j] = q + 1;
			}
		}
		for (int j = 0, k = 0; j < (int)vr[i].size(); j++) {
			buck[vr[i][j]].push_back(make_pair(i, &sr[i][j]));
			while (k < (int)vl[i].size() && a[vr[i][j]] < a[vl[i][k]]) k++;
			if (k < (int)vl[i].size()) {
				buck[vr[i][j]].push_back(make_pair(vl[i][k], &tr[i][j]));
			} else {
				tr[i][j] = q + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) bit[i] = q + 1;
	for (int i = n; i >= 1; i--) {
		for (auto &P : buckq[i]) {
			add(P.first, P.second);
		}
		for (auto &P : buck[i]) {
			*P.second = qry(P.first);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (int)vl[i].size(); j++) {
			int L = sl[i][j], R = min(j < (int)vl[i].size() - 1 ? sl[i][j + 1] : q + 1, tl[i][j]);
			if (L < R) ans[L]++, ans[R]--;
		}
		for (int j = 0; j < (int)vr[i].size(); j++) {
			int L = sr[i][j], R = min(j < (int)vr[i].size() - 1 ? sr[i][j + 1] : q + 1, tr[i][j]);
			if (L < R) ans[L]++, ans[R]--;
		}
	}
	for (int i = 1; i <= q; i++) ans[i] += ans[i - 1];
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}
```