#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;
typedef pair <pii, int> ppi;

const int B = 158;

int a[25010], p[25010], L[100010], R[100010], T[25010];
vector <int> all[25010], val[2][25010];
vector <pii> op;
set <int> S;
vector <ppi> qry;
vector <ppi> mdy;
int n, q;
int ans[100010];

void modify(int x, int v) {while (x <= n) T[x] = min(T[x], v), x += x & -x;}

int query(int x) {int res = q; while (x) res = min(res, T[x]), x -= x & -x; return res;}

bool cmp(const pii &a, const pii &b) {
	return a.fi / B != b.fi / B ? a.fi < b.fi : a.se < b.se;
}

void Insert(int x) {
	set <int> :: iterator it = S.lower_bound(a[x]);
	if (it != S.end()) all[x].push_back(p[*it]);
	if (it != S.begin()) it--, all[p[*it]].push_back(x);
	S.insert(a[x]);
}

void Erase(int x) {
	S.erase(a[x]); set <int> :: iterator it = S.lower_bound(a[x]);
	if (it != S.end() && it != S.begin()) {
		int suc = *it; it--; int pre = *it;
		all[p[pre]].push_back(p[suc]);
	}
}

bool IsSmall(const int &x, const int &y) {return a[x] < a[y];}

bool IsBig(const int &x, const int &y) {return a[x] > a[y];}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), p[a[i]] = i;
	for (int i = 0; i < q; i++) scanf("%d%d", &L[i], &R[i]), op.push_back(mp(L[i], R[i]));
	for (int i = 0; i < q; i++) mdy.push_back(mp(mp(L[i], R[i]), i));
	sort(op.begin(), op.end(), cmp);
	int L = 1, R = 0;
	for (int i = 0; i < op.size(); i++) {
		int l = op[i].fi, r = op[i].se;
		while (L > l) Insert(--L);
		while (R < r) Insert(++R);
		while (L < l) Erase(L++);
		while (R > r) Erase(R--);
	}
	for (int i = 1; i <= n; i++) {
		sort(all[i].begin(), all[i].end());
		all[i].resize(unique(all[i].begin(), all[i].end()) - all[i].begin());
		int pos = lower_bound(all[i].begin(), all[i].end(), i) - all[i].begin();
		for (int j = 0; j < all[i].size(); j++) {
			qry.push_back(mp(mp(min(i, all[i][j]), max(all[i][j], i)), i << 2));
		}
		for (int j = 0; j < pos; j++) {
			int x = all[i][j]; auto it = lower_bound(all[i].begin() + pos, all[i].end(), x, IsBig);
			if (it != all[i].end()) qry.push_back(mp(mp(x, *it), i << 2 | 1));
		}
		for (int j = pos; j < all[i].size(); j++) {
			int x = all[i][j]; auto it = lower_bound(all[i].rend() - pos, all[i].rend(), x, IsBig);
			if (it != all[i].rend()) qry.push_back(mp(mp(*it, x), i << 2 | 2));
		}
		val[0][i].resize(all[i].size());
		val[1][i].resize(all[i].size(), q);
	}
	sort(qry.begin(), qry.end()), sort(mdy.rbegin(), mdy.rend());
	memset(T, 0x3f, sizeof(T));
	for (int i = 0; i < qry.size(); i++) {
		int l = qry[i].fi.fi, r = qry[i].fi.se, d = qry[i].se & 3, p = qry[i].se >> 2;
		while (mdy.size() && mdy.back().fi.fi <= l) {
			modify(n - mdy.back().fi.se + 1, mdy.back().se), mdy.pop_back();
		}
		int nxt = d == 0 ? l + r - p : d == 1 ? l : r;
		if (d == 2) d = 1;
		val[d][p][lower_bound(all[p].begin(), all[p].end(), nxt) - all[p].begin()] = query(n - r + 1);
	}
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(all[i].begin(), all[i].end(), i) - all[i].begin();
		for (int j = 0; j < pos; j++) {
			int l = val[0][i][j], r = val[1][i][j];
			if (j) r = min(r, val[0][i][j - 1]);
			if (l < r) ans[l]++, ans[r]--;
		}
		for (int j = pos; j < all[i].size(); j++) {
			int l = val[0][i][j], r = val[1][i][j];
			if (j + 1 < all[i].size()) r = min(r, val[0][i][j + 1]);
			if (l < r) assert(r <= q), ans[l]++, ans[r]--;
		}
	}
	for (int i = 0; i < q; i++) ans[i + 1] += ans[i];
	for (int i = 0; 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>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;
typedef pair <pii, int> ppi;

const int B = 158;

int a[25010], p[25010], L[100010], R[100010], T[25010];
vector <int> all[25010], val[2][25010];
vector <pii> op;
set <int> S;
vector <ppi> qry;
vector <ppi> mdy;
int n, q;
int ans[100010];

void modify(int x, int v) {while (x <= n) T[x] = min(T[x], v), x += x & -x;}

int query(int x) {int res = q; while (x) res = min(res, T[x]), x -= x & -x; return res;}

bool cmp(const pii &a, const pii &b) {
	return a.fi / B != b.fi / B ? a.fi < b.fi : a.se < b.se;
}

void Insert(int x) {
	set <int> :: iterator it = S.lower_bound(a[x]);
	if (it != S.end()) all[x].push_back(p[*it]);
	if (it != S.begin()) it--, all[p[*it]].push_back(x);
	S.insert(a[x]);
}

void Erase(int x) {
	S.erase(a[x]); set <int> :: iterator it = S.lower_bound(a[x]);
	if (it != S.end() && it != S.begin()) {
		int suc = *it; it--; int pre = *it;
		all[p[pre]].push_back(p[suc]);
	}
}

bool IsSmall(const int &x, const int &y) {return a[x] < a[y];}

bool IsBig(const int &x, const int &y) {return a[x] > a[y];}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), p[a[i]] = i;
	for (int i = 0; i < q; i++) scanf("%d%d", &L[i], &R[i]), op.push_back(mp(L[i], R[i]));
	for (int i = 0; i < q; i++) mdy.push_back(mp(mp(L[i], R[i]), i));
	sort(op.begin(), op.end(), cmp);
	int L = 1, R = 0;
	for (int i = 0; i < op.size(); i++) {
		int l = op[i].fi, r = op[i].se;
		while (L > l) Insert(--L);
		while (R < r) Insert(++R);
		while (L < l) Erase(L++);
		while (R > r) Erase(R--);
	}
	for (int i = 1; i <= n; i++) {
		sort(all[i].begin(), all[i].end());
		all[i].resize(unique(all[i].begin(), all[i].end()) - all[i].begin());
		int pos = lower_bound(all[i].begin(), all[i].end(), i) - all[i].begin();
		for (int j = 0; j < all[i].size(); j++) {
			qry.push_back(mp(mp(min(i, all[i][j]), max(all[i][j], i)), i << 2));
		}
		for (int j = 0; j < pos; j++) {
			int x = all[i][j]; auto it = lower_bound(all[i].begin() + pos, all[i].end(), x, IsBig);
			if (it != all[i].end()) qry.push_back(mp(mp(x, *it), i << 2 | 1));
		}
		for (int j = pos; j < all[i].size(); j++) {
			int x = all[i][j]; auto it = lower_bound(all[i].rend() - pos, all[i].rend(), x, IsBig);
			if (it != all[i].rend()) qry.push_back(mp(mp(*it, x), i << 2 | 2));
		}
		val[0][i].resize(all[i].size());
		val[1][i].resize(all[i].size(), q);
	}
	sort(qry.begin(), qry.end()), sort(mdy.rbegin(), mdy.rend());
	memset(T, 0x3f, sizeof(T));
	for (int i = 0; i < qry.size(); i++) {
		int l = qry[i].fi.fi, r = qry[i].fi.se, d = qry[i].se & 3, p = qry[i].se >> 2;
		while (mdy.size() && mdy.back().fi.fi <= l) {
			modify(n - mdy.back().fi.se + 1, mdy.back().se), mdy.pop_back();
		}
		int nxt = d == 0 ? l + r - p : d == 1 ? l : r;
		if (d == 2) d = 1;
		val[d][p][lower_bound(all[p].begin(), all[p].end(), nxt) - all[p].begin()] = query(n - r + 1);
	}
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(all[i].begin(), all[i].end(), i) - all[i].begin();
		for (int j = 0; j < pos; j++) {
			int l = val[0][i][j], r = val[1][i][j];
			if (j) r = min(r, val[0][i][j - 1]);
			if (l < r) ans[l]++, ans[r]--;
		}
		for (int j = pos; j < all[i].size(); j++) {
			int l = val[0][i][j], r = val[1][i][j];
			if (j + 1 < all[i].size()) r = min(r, val[0][i][j + 1]);
			if (l < r) assert(r <= q), ans[l]++, ans[r]--;
		}
	}
	for (int i = 0; i < q; i++) ans[i + 1] += ans[i];
	for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
	return 0;
}

```