/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAGIC=125;
unordered_map<int,int> queries[25000+233];
int n,q,a[25000+233],pos[25000+233],l[100000+233],r[100000+233],id[100000+233],ans[100000+233];
vector<int> tol[25000+233],tor[25000+233];
bool cmp(int A,int B){
	if(l[A]/MAGIC==l[B]/MAGIC) return r[A]<r[B];
	return l[A]/MAGIC<l[B]/MAGIC;
}
bool cmp2(int A,int B){
	return II(l[A],r[A])<II(l[B],r[B]);
}
void addedge(int u,int v){
	if(pos[u]<pos[v]) tor[pos[u]].PB(pos[v]);
	if(pos[u]>pos[v]) tol[pos[u]].PB(pos[v]);
}
int bit[25000+233];
void Set(int x,int val){
	while(x<=25000){
		check_min(bit[x],val);
		x+=x&-x;
	}
}
int query(int x){
	int rest=q+1;
	while(x){
		check_min(rest,bit[x]);
		x-=x&-x;
	}
	return rest;
}
void solve(){
	memset(bit,63,sizeof(bit));
	rb(i,1,q) id[i]=i;
	sort(id+1,id+1+q,cmp2);
	int pt=1;
	rb(i,1,n){
		while(pt<=q&&l[id[pt]]<=i){
			Set(n-r[id[pt]]+1,id[pt]);
			++pt;
		}
		for(auto ite=queries[i].begin();ite!=queries[i].end();ite++){
			ite->SEC=query(n-ite->FIR+1);
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	rb(i,1,n) scanf("%d",&a[i]),pos[a[i]]=i;
	rb(i,1,q) id[i]=i;
	rb(i,1,q) scanf("%d%d",&l[i],&r[i]);
	sort(id+1,id+1+q,cmp);
	set<int> s;
	int nowl,nowr;
	nowl=nowr=0;
	rb(i_,1,q){
		int i=id[i_];
		while(nowr<r[i]) {
		++nowr;
		s.insert(a[nowr]);
		auto ite=s.find(a[nowr]);
		if(ite!=s.begin()) addedge(*prev(ite),*ite);
		if(next(ite)!=s.end()) addedge(*ite,*next(ite));
		}
		while(nowl<l[i]) {
		if(nowl){
			auto ite=s.find(a[nowl]);
			if(ite!=s.begin()&&next(ite)!=s.end()) addedge(*prev(ite),*next(ite));
			s.erase(a[nowl]);
		}
		++nowl;
		}
		while(nowr>r[i]){
		auto ite=s.find(a[nowr]);
		if(ite!=s.begin()&&next(ite)!=s.end()) addedge(*prev(ite),*next(ite));
		s.erase(a[nowr]);--nowr;
		}
		while(nowl>l[i]) {--nowl;
		s.insert(a[nowl]);
		auto ite=s.find(a[nowl]);
		if(ite!=s.begin()) addedge(*prev(ite),*ite);
		if(next(ite)!=s.end()) addedge(*ite,*next(ite));
		}
	}
	rb(i,1,n) sort(ALL(tol[i])),sort(ALL(tor[i])),tol[i].erase(unique(ALL(tol[i])),tol[i].end()),
	          tor[i].erase(unique(ALL(tor[i])),tor[i].end()),reverse(ALL(tol[i]));
	rb(i,1,n){
		rep(j,tol[i].size()) queries[tol[i][j]][i]=1;
		rep(j,tor[i].size()) queries[i][tor[i][j]]=1;
		int pt=0;
		rep(j,tol[i].size()){
			while(pt<tor[i].size()&&a[tor[i][pt]]>a[tol[i][j]]) ++pt;
			if(pt<tor[i].size()) queries[min(tol[i][j],tor[i][pt])][max(tol[i][j],tor[i][pt])]=1;
		}
		pt=0;
		rep(j,tor[i].size()){
			while(pt<tol[i].size()&&a[tol[i][pt]]>a[tor[i][j]]) ++pt;
			if(pt<tol[i].size()) queries[min(tor[i][j],tol[i][pt])][max(tor[i][j],tol[i][pt])]=1;
		}
	}
	int cnt=0;
	rb(i,1,n) cnt+=tor[i].size()+tol[i].size();
	solve();
	rb(i,1,n){
		int pt=0;
		rep(j,tol[i].size()){
			int Z=q+1;
			while(pt<tor[i].size()&&a[tor[i][pt]]>a[tol[i][j]]) ++pt;
			if(pt<tor[i].size()) check_min(Z,queries[min(tol[i][j],tor[i][pt])][max(tol[i][j],tor[i][pt])]);
			if(j!=tol[i].size()-1) check_min(Z,queries[tol[i][j+1]][i]);
			if(Z>queries[tol[i][j]][i]){
				ans[queries[tol[i][j]][i]]++;
				ans[Z]--;
			}
		}
		pt=0;
		rep(j,tor[i].size()){
			int Z=q+1;
			while(pt<tol[i].size()&&a[tol[i][pt]]>a[tor[i][j]]) ++pt;
			if(pt<tol[i].size()) check_min(Z,queries[min(tor[i][j],tol[i][pt])][max(tor[i][j],tol[i][pt])]);
			if(j!=tor[i].size()-1) check_min(Z,queries[i][tor[i][j+1]]);
			if(Z>queries[i][tor[i][j]]){
				ans[queries[i][tor[i][j]]]++;
				ans[Z]--;
			}
		}
	}
	int rest=0;
	rb(i,1,q){
		rest+=ans[i];
		printf("%d\n",rest);
	}
	return 0;
}
### Prompt

Your task is to create 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
/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAGIC=125;
unordered_map<int,int> queries[25000+233];
int n,q,a[25000+233],pos[25000+233],l[100000+233],r[100000+233],id[100000+233],ans[100000+233];
vector<int> tol[25000+233],tor[25000+233];
bool cmp(int A,int B){
	if(l[A]/MAGIC==l[B]/MAGIC) return r[A]<r[B];
	return l[A]/MAGIC<l[B]/MAGIC;
}
bool cmp2(int A,int B){
	return II(l[A],r[A])<II(l[B],r[B]);
}
void addedge(int u,int v){
	if(pos[u]<pos[v]) tor[pos[u]].PB(pos[v]);
	if(pos[u]>pos[v]) tol[pos[u]].PB(pos[v]);
}
int bit[25000+233];
void Set(int x,int val){
	while(x<=25000){
		check_min(bit[x],val);
		x+=x&-x;
	}
}
int query(int x){
	int rest=q+1;
	while(x){
		check_min(rest,bit[x]);
		x-=x&-x;
	}
	return rest;
}
void solve(){
	memset(bit,63,sizeof(bit));
	rb(i,1,q) id[i]=i;
	sort(id+1,id+1+q,cmp2);
	int pt=1;
	rb(i,1,n){
		while(pt<=q&&l[id[pt]]<=i){
			Set(n-r[id[pt]]+1,id[pt]);
			++pt;
		}
		for(auto ite=queries[i].begin();ite!=queries[i].end();ite++){
			ite->SEC=query(n-ite->FIR+1);
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	rb(i,1,n) scanf("%d",&a[i]),pos[a[i]]=i;
	rb(i,1,q) id[i]=i;
	rb(i,1,q) scanf("%d%d",&l[i],&r[i]);
	sort(id+1,id+1+q,cmp);
	set<int> s;
	int nowl,nowr;
	nowl=nowr=0;
	rb(i_,1,q){
		int i=id[i_];
		while(nowr<r[i]) {
		++nowr;
		s.insert(a[nowr]);
		auto ite=s.find(a[nowr]);
		if(ite!=s.begin()) addedge(*prev(ite),*ite);
		if(next(ite)!=s.end()) addedge(*ite,*next(ite));
		}
		while(nowl<l[i]) {
		if(nowl){
			auto ite=s.find(a[nowl]);
			if(ite!=s.begin()&&next(ite)!=s.end()) addedge(*prev(ite),*next(ite));
			s.erase(a[nowl]);
		}
		++nowl;
		}
		while(nowr>r[i]){
		auto ite=s.find(a[nowr]);
		if(ite!=s.begin()&&next(ite)!=s.end()) addedge(*prev(ite),*next(ite));
		s.erase(a[nowr]);--nowr;
		}
		while(nowl>l[i]) {--nowl;
		s.insert(a[nowl]);
		auto ite=s.find(a[nowl]);
		if(ite!=s.begin()) addedge(*prev(ite),*ite);
		if(next(ite)!=s.end()) addedge(*ite,*next(ite));
		}
	}
	rb(i,1,n) sort(ALL(tol[i])),sort(ALL(tor[i])),tol[i].erase(unique(ALL(tol[i])),tol[i].end()),
	          tor[i].erase(unique(ALL(tor[i])),tor[i].end()),reverse(ALL(tol[i]));
	rb(i,1,n){
		rep(j,tol[i].size()) queries[tol[i][j]][i]=1;
		rep(j,tor[i].size()) queries[i][tor[i][j]]=1;
		int pt=0;
		rep(j,tol[i].size()){
			while(pt<tor[i].size()&&a[tor[i][pt]]>a[tol[i][j]]) ++pt;
			if(pt<tor[i].size()) queries[min(tol[i][j],tor[i][pt])][max(tol[i][j],tor[i][pt])]=1;
		}
		pt=0;
		rep(j,tor[i].size()){
			while(pt<tol[i].size()&&a[tol[i][pt]]>a[tor[i][j]]) ++pt;
			if(pt<tol[i].size()) queries[min(tor[i][j],tol[i][pt])][max(tor[i][j],tol[i][pt])]=1;
		}
	}
	int cnt=0;
	rb(i,1,n) cnt+=tor[i].size()+tol[i].size();
	solve();
	rb(i,1,n){
		int pt=0;
		rep(j,tol[i].size()){
			int Z=q+1;
			while(pt<tor[i].size()&&a[tor[i][pt]]>a[tol[i][j]]) ++pt;
			if(pt<tor[i].size()) check_min(Z,queries[min(tol[i][j],tor[i][pt])][max(tol[i][j],tor[i][pt])]);
			if(j!=tol[i].size()-1) check_min(Z,queries[tol[i][j+1]][i]);
			if(Z>queries[tol[i][j]][i]){
				ans[queries[tol[i][j]][i]]++;
				ans[Z]--;
			}
		}
		pt=0;
		rep(j,tor[i].size()){
			int Z=q+1;
			while(pt<tol[i].size()&&a[tol[i][pt]]>a[tor[i][j]]) ++pt;
			if(pt<tol[i].size()) check_min(Z,queries[min(tor[i][j],tol[i][pt])][max(tor[i][j],tol[i][pt])]);
			if(j!=tor[i].size()-1) check_min(Z,queries[i][tor[i][j+1]]);
			if(Z>queries[i][tor[i][j]]){
				ans[queries[i][tor[i][j]]]++;
				ans[Z]--;
			}
		}
	}
	int rest=0;
	rb(i,1,q){
		rest+=ans[i];
		printf("%d\n",rest);
	}
	return 0;
}
```