#include <bits/stdc++.h>
using namespace std;

#define LL long long

const int maxN = 1e5 + 10, INF = 1e9;

struct Node
{
	int l, r, id;
}q[maxN + 1];

struct Query
{
	int a, b, c, id;
	Query(int A = 0, int B = 0, int C = 0, int ID = 0) { a = A, b = B, c = C, id = ID; }
};

int n, m;
int bel[maxN + 1], B;
int p[maxN + 1], pos[maxN + 1];
int C[maxN + 1];
LL ans[maxN + 1];

set<int> s;

vector<int> vec[maxN + 1];
vector<int> L, R;
vector<Query> A;

inline int read()
{
	int num = 0, f = 1;
	char ch = getchar();
	while( !isdigit( ch ) ) { if(ch == '-') f = -1; ch = getchar(); }
	while( isdigit( ch ) ) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
	return num * f;
}

inline bool cmp(Node a, Node b)
{
	return bel[a.l] ^ bel[b.l] ? bel[a.l] < bel[b.l] : bel[a.l] & 1 ? a.r < b.r : a.r > b.r;
}

inline void add(int x)
{
	set<int>::iterator it = (s.insert(p[x])).first;
	if(next(it) != s.end()) vec[*it].push_back(*next(it));
	if(it != s.begin()) vec[*prev(it)].push_back(*it);
}

inline void del(int x)
{
	s.erase(p[x]);
	set<int>::iterator it = s.lower_bound(p[x]);
	if(it != s.end() && it != s.begin())
		vec[*prev(it)].push_back(*it);
}

inline bool cmp2(Query a, Query b)
{
	if(a.a == b.a) return a.id < b.id;
	return a.a > b.a;
}

inline int lowbit(int x) { return x & -x; }

inline void change(int x, int v)
{
	for(int i = x; i <= n; i += lowbit(i)) C[i] = min(C[i], v);
}

inline int query(int x)
{
	int ans = INF;
	for(int i = x; i; i ^= lowbit(i)) ans = min(ans, C[i]);	
	return ans;
}

int main()
{
	n = read(), m = read();
	B = max(1.0, n / sqrt((double)m * 2 / 3));
	for(int i = 1; i <= n; i++) 
	{
		p[i] = read();
		bel[i] = (i - 1) / B + 1;
		pos[ p[i] ] = i;
	}

	for(int i = 1; i <= m; i++)
	{
		q[i].l = read(), q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);

	int l = 1, r = 0;
	for(int i = 1; i <= m; i++)
	{
		while(l > q[i].l) add(-- l);
		while(r < q[i].r) add(++ r);
		while(l < q[i].l) del(l ++);
		while(r > q[i].r) del(r --);
	}

	int ct = 0;
	for(int i = 1; i <= n; i++)
	{
		sort(vec[i].begin(), vec[i].end());
		vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());
		vector<int> vl, vr;
		for(int j = vec[i].size() - 1; j >= 0; j--)
			if(pos[ vec[i][j] ] < pos[i]) vl.push_back(vec[i][j]);
			else vr.push_back(vec[i][j]);
		int now = 0;
		for(int j = 0; j < vr.size(); j++)
		{
			while(now < vl.size() && vl[now] > vr[j]) now ++;
			ct ++;
			L.push_back(INF); R.push_back(INF);
			int l = pos[i], r = pos[ vr[j] ];
			A.push_back( Query(r, l, 0, ct) );
			if(j != vr.size() - 1)
			{
				l = pos[i], r = pos[ vr[j + 1] ];
				A.push_back( Query(r, l, 1, ct) );
			}
			if(now != vl.size())
			{
				l = pos[ vl[now] ], r = pos[ vr[j] ];
				A.push_back( Query(r, l, 1, ct) );
			}
		}
		now = 0;
		for(int j = 0; j < vl.size(); j++)
		{
			while(now < vr.size() && vr[now] > vl[j]) now ++;
			ct ++;
			L.push_back(INF); R.push_back(INF);
			int l = pos[ vl[j] ], r = pos[i];
			A.push_back( Query(r, l, 0, ct) );
			if(j != vl.size() - 1)
			{
				l = pos[ vl[j + 1] ], r = pos[i];
				A.push_back( Query(r, l, 1, ct) );
			}
			if(now != vr.size())
			{
				l = pos[ vl[j] ], r = pos[ vr[now] ];
				A.push_back( Query(r, l, 1, ct) );
			}
		}		
	}
	for(int i = 1; i <= m; i++) A.push_back( Query(q[i].r, q[i].l, q[i].id, 0) );

	for(int i = 1; i <= n; i++) C[i] = INF;
	sort(A.begin(), A.end(), cmp2);
	for(int i = 0; i < A.size(); i++)
		if(!A[i].id) change(A[i].b, A[i].c);
		else
		{
			if(!A[i].c) L[ A[i].id - 1 ] = min(L[ A[i].id - 1 ], query(A[i].b));
			else R[ A[i].id - 1 ] = min(R[ A[i].id - 1 ], query(A[i].b));
		}

	for(int i = 0; i < ct; i++)
	{
		if(L[i] >= R[i]) continue;
		if(L[i] != INF) ans[ L[i] ] ++; 
		if(R[i] != INF) ans[ R[i] ] --;
	}

	for(int i = 1; i <= m; i++)
	{
		ans[i] += ans[i - 1];
		printf("%lld\n", ans[i]);
	}
	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 = 1e5 + 10, INF = 1e9;

struct Node
{
	int l, r, id;
}q[maxN + 1];

struct Query
{
	int a, b, c, id;
	Query(int A = 0, int B = 0, int C = 0, int ID = 0) { a = A, b = B, c = C, id = ID; }
};

int n, m;
int bel[maxN + 1], B;
int p[maxN + 1], pos[maxN + 1];
int C[maxN + 1];
LL ans[maxN + 1];

set<int> s;

vector<int> vec[maxN + 1];
vector<int> L, R;
vector<Query> A;

inline int read()
{
	int num = 0, f = 1;
	char ch = getchar();
	while( !isdigit( ch ) ) { if(ch == '-') f = -1; ch = getchar(); }
	while( isdigit( ch ) ) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
	return num * f;
}

inline bool cmp(Node a, Node b)
{
	return bel[a.l] ^ bel[b.l] ? bel[a.l] < bel[b.l] : bel[a.l] & 1 ? a.r < b.r : a.r > b.r;
}

inline void add(int x)
{
	set<int>::iterator it = (s.insert(p[x])).first;
	if(next(it) != s.end()) vec[*it].push_back(*next(it));
	if(it != s.begin()) vec[*prev(it)].push_back(*it);
}

inline void del(int x)
{
	s.erase(p[x]);
	set<int>::iterator it = s.lower_bound(p[x]);
	if(it != s.end() && it != s.begin())
		vec[*prev(it)].push_back(*it);
}

inline bool cmp2(Query a, Query b)
{
	if(a.a == b.a) return a.id < b.id;
	return a.a > b.a;
}

inline int lowbit(int x) { return x & -x; }

inline void change(int x, int v)
{
	for(int i = x; i <= n; i += lowbit(i)) C[i] = min(C[i], v);
}

inline int query(int x)
{
	int ans = INF;
	for(int i = x; i; i ^= lowbit(i)) ans = min(ans, C[i]);	
	return ans;
}

int main()
{
	n = read(), m = read();
	B = max(1.0, n / sqrt((double)m * 2 / 3));
	for(int i = 1; i <= n; i++) 
	{
		p[i] = read();
		bel[i] = (i - 1) / B + 1;
		pos[ p[i] ] = i;
	}

	for(int i = 1; i <= m; i++)
	{
		q[i].l = read(), q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);

	int l = 1, r = 0;
	for(int i = 1; i <= m; i++)
	{
		while(l > q[i].l) add(-- l);
		while(r < q[i].r) add(++ r);
		while(l < q[i].l) del(l ++);
		while(r > q[i].r) del(r --);
	}

	int ct = 0;
	for(int i = 1; i <= n; i++)
	{
		sort(vec[i].begin(), vec[i].end());
		vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());
		vector<int> vl, vr;
		for(int j = vec[i].size() - 1; j >= 0; j--)
			if(pos[ vec[i][j] ] < pos[i]) vl.push_back(vec[i][j]);
			else vr.push_back(vec[i][j]);
		int now = 0;
		for(int j = 0; j < vr.size(); j++)
		{
			while(now < vl.size() && vl[now] > vr[j]) now ++;
			ct ++;
			L.push_back(INF); R.push_back(INF);
			int l = pos[i], r = pos[ vr[j] ];
			A.push_back( Query(r, l, 0, ct) );
			if(j != vr.size() - 1)
			{
				l = pos[i], r = pos[ vr[j + 1] ];
				A.push_back( Query(r, l, 1, ct) );
			}
			if(now != vl.size())
			{
				l = pos[ vl[now] ], r = pos[ vr[j] ];
				A.push_back( Query(r, l, 1, ct) );
			}
		}
		now = 0;
		for(int j = 0; j < vl.size(); j++)
		{
			while(now < vr.size() && vr[now] > vl[j]) now ++;
			ct ++;
			L.push_back(INF); R.push_back(INF);
			int l = pos[ vl[j] ], r = pos[i];
			A.push_back( Query(r, l, 0, ct) );
			if(j != vl.size() - 1)
			{
				l = pos[ vl[j + 1] ], r = pos[i];
				A.push_back( Query(r, l, 1, ct) );
			}
			if(now != vr.size())
			{
				l = pos[ vl[j] ], r = pos[ vr[now] ];
				A.push_back( Query(r, l, 1, ct) );
			}
		}		
	}
	for(int i = 1; i <= m; i++) A.push_back( Query(q[i].r, q[i].l, q[i].id, 0) );

	for(int i = 1; i <= n; i++) C[i] = INF;
	sort(A.begin(), A.end(), cmp2);
	for(int i = 0; i < A.size(); i++)
		if(!A[i].id) change(A[i].b, A[i].c);
		else
		{
			if(!A[i].c) L[ A[i].id - 1 ] = min(L[ A[i].id - 1 ], query(A[i].b));
			else R[ A[i].id - 1 ] = min(R[ A[i].id - 1 ], query(A[i].b));
		}

	for(int i = 0; i < ct; i++)
	{
		if(L[i] >= R[i]) continue;
		if(L[i] != INF) ans[ L[i] ] ++; 
		if(R[i] != INF) ans[ R[i] ] --;
	}

	for(int i = 1; i <= m; i++)
	{
		ans[i] += ans[i - 1];
		printf("%lld\n", ans[i]);
	}
	return 0;
}

```