#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<int> vi;
const int MN = 25005;
const int MQ = 100005;
const int D = 100;
int n, q;
int a[MN], pos[MN];
int l[MQ], r[MQ], que[MQ];
set<int> S;
vector<array<int, 3>> eve[MN];
vp add[MN];
vp edges;
vp l_edge[MN], r_edge[MN];
vi in, out;
int rlt[MQ];

struct fenwick_tree {
    int bit[MN];
 
    void init() {
        fill(bit + 1, bit + n + 1, MQ);
    }
 
    void update(int u, int v) {
        for (; u > 0; u -= u & -u) {
            bit[u] = min(bit[u], v);
        }
    }
    
    int query(int u) {
        int ans = MQ;
        for (; u <= n; u += u & -u) {
            ans = min(ans, bit[u]);
        }
        return ans;
    }
} bit;

inline void add_node(int u) {
	auto it = S.insert(u).first;
	if (it != S.begin()) edges.push_back({*prev(it), u});
	if (next(it) != S.end()) edges.push_back({u, *next(it)});
}

inline void remove_node(int u) {
	S.erase(u);
	auto it = S.lower_bound(u);
	if (it != S.begin() && it != S.end()) edges.push_back({*prev(it), *it});
}

void find_edge() {
	for (int i = 1; i <= q; i++) que[i] = i;
	sort(que + 1, que + q + 1, [](const int i, const int j) { return (l[i] / D != l[j] / D ? l[i] < l[j] : r[i] < r[j]); });
	int le = 1, ri = 0;
	for (int i = 1; i <= q; i++) {
		int gl = l[que[i]], gr = r[que[i]];
		while (ri < gr) add_node(a[++ri]);
		while (le > gl) add_node(a[--le]);
		while (ri > gr) remove_node(a[ri--]);
		while (le < gl) remove_node(a[le++]);
	}
	sort(edges.begin(), edges.end());
	edges.erase(unique(edges.begin(), edges.end()), edges.end());
	in = vi(edges.size(), MQ - 1);
	out = vi(edges.size(), MQ - 1);
}

void find() {
	for (int i = 0; i < edges.size(); i++) {
		int u = edges[i].first, v = edges[i].second;
		int iu = pos[u], iv = pos[v];
		if (iu < iv) r_edge[iu].push_back({iv, i});
		else l_edge[iu].push_back({iv, i});
	}
	for (int u = 1; u <= n; u++) {
		vp& ri = r_edge[u], le = l_edge[u];
		reverse(ri.begin(), ri.end());
		reverse(le.begin(), le.end());
		le.push_back({0, -1});
		ri.push_back({n + 1, -1});
		int l = 0, r = 0;
		while (l != le.size() - 1 || r != ri.size() - 1) {
			if (a[le[l].first] < a[ri[r].first]) {
				int ur = ri[r].first, i = ri[r].second;
				int t = le[l].first;
				int ur1 = ri[r + 1].first;
				eve[u].push_back({ur, i, 0});
				eve[u].push_back({ur1, i, 1});
				eve[t].push_back({ur, i, 1});
				r++;
			}
			else {
				int ul = le[l].first, i = le[l].second;
				int t = ri[r].first;
				int ul1 = le[l + 1].first;
				eve[ul].push_back({u, i, 0});
				eve[ul1].push_back({u, i, 1});
				eve[ul].push_back({t, i, 1});
				l++;
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= q; i++) add[l[i]].push_back({r[i], i});
	bit.init();
	for (int i = 1; i <= n; i++) {
		for (auto pp : add[i]) {
			int u = pp.first, r = pp.second;
			bit.update(u, r);
		}
		for (auto pp : eve[i]) {
			int u = pp[0], v = pp[1], t = pp[2];
			int &cur = (t == 0 ? in[v] : out[v]);
			cur = min(cur, bit.query(u));
		}
	}
	for (int i = 0; i < edges.size(); i++) {
		rlt[in[i]]++;
		rlt[out[i]]--;
	}
	for (int i = 1; i <= q; i++) {
		rlt[i] += rlt[i - 1];
		cout << rlt[i] << endl;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	for (int i = 1; i <= q; i++) cin >> l[i] >> r[i];
	find_edge();
	find();
	solve();
	
	return 0;

}


### Prompt

Your challenge is to write 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 endl '\n'
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<int> vi;
const int MN = 25005;
const int MQ = 100005;
const int D = 100;
int n, q;
int a[MN], pos[MN];
int l[MQ], r[MQ], que[MQ];
set<int> S;
vector<array<int, 3>> eve[MN];
vp add[MN];
vp edges;
vp l_edge[MN], r_edge[MN];
vi in, out;
int rlt[MQ];

struct fenwick_tree {
    int bit[MN];
 
    void init() {
        fill(bit + 1, bit + n + 1, MQ);
    }
 
    void update(int u, int v) {
        for (; u > 0; u -= u & -u) {
            bit[u] = min(bit[u], v);
        }
    }
    
    int query(int u) {
        int ans = MQ;
        for (; u <= n; u += u & -u) {
            ans = min(ans, bit[u]);
        }
        return ans;
    }
} bit;

inline void add_node(int u) {
	auto it = S.insert(u).first;
	if (it != S.begin()) edges.push_back({*prev(it), u});
	if (next(it) != S.end()) edges.push_back({u, *next(it)});
}

inline void remove_node(int u) {
	S.erase(u);
	auto it = S.lower_bound(u);
	if (it != S.begin() && it != S.end()) edges.push_back({*prev(it), *it});
}

void find_edge() {
	for (int i = 1; i <= q; i++) que[i] = i;
	sort(que + 1, que + q + 1, [](const int i, const int j) { return (l[i] / D != l[j] / D ? l[i] < l[j] : r[i] < r[j]); });
	int le = 1, ri = 0;
	for (int i = 1; i <= q; i++) {
		int gl = l[que[i]], gr = r[que[i]];
		while (ri < gr) add_node(a[++ri]);
		while (le > gl) add_node(a[--le]);
		while (ri > gr) remove_node(a[ri--]);
		while (le < gl) remove_node(a[le++]);
	}
	sort(edges.begin(), edges.end());
	edges.erase(unique(edges.begin(), edges.end()), edges.end());
	in = vi(edges.size(), MQ - 1);
	out = vi(edges.size(), MQ - 1);
}

void find() {
	for (int i = 0; i < edges.size(); i++) {
		int u = edges[i].first, v = edges[i].second;
		int iu = pos[u], iv = pos[v];
		if (iu < iv) r_edge[iu].push_back({iv, i});
		else l_edge[iu].push_back({iv, i});
	}
	for (int u = 1; u <= n; u++) {
		vp& ri = r_edge[u], le = l_edge[u];
		reverse(ri.begin(), ri.end());
		reverse(le.begin(), le.end());
		le.push_back({0, -1});
		ri.push_back({n + 1, -1});
		int l = 0, r = 0;
		while (l != le.size() - 1 || r != ri.size() - 1) {
			if (a[le[l].first] < a[ri[r].first]) {
				int ur = ri[r].first, i = ri[r].second;
				int t = le[l].first;
				int ur1 = ri[r + 1].first;
				eve[u].push_back({ur, i, 0});
				eve[u].push_back({ur1, i, 1});
				eve[t].push_back({ur, i, 1});
				r++;
			}
			else {
				int ul = le[l].first, i = le[l].second;
				int t = ri[r].first;
				int ul1 = le[l + 1].first;
				eve[ul].push_back({u, i, 0});
				eve[ul1].push_back({u, i, 1});
				eve[ul].push_back({t, i, 1});
				l++;
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= q; i++) add[l[i]].push_back({r[i], i});
	bit.init();
	for (int i = 1; i <= n; i++) {
		for (auto pp : add[i]) {
			int u = pp.first, r = pp.second;
			bit.update(u, r);
		}
		for (auto pp : eve[i]) {
			int u = pp[0], v = pp[1], t = pp[2];
			int &cur = (t == 0 ? in[v] : out[v]);
			cur = min(cur, bit.query(u));
		}
	}
	for (int i = 0; i < edges.size(); i++) {
		rlt[in[i]]++;
		rlt[out[i]]--;
	}
	for (int i = 1; i <= q; i++) {
		rlt[i] += rlt[i - 1];
		cout << rlt[i] << endl;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	for (int i = 1; i <= q; i++) cin >> l[i] >> r[i];
	find_edge();
	find();
	solve();
	
	return 0;

}


```