#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
#define pii std::pair<LL,LL>
const LL maxn=1e6+9,mod=998244353,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
LL add(LL x,LL y){
	return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
	}return ret;
}
struct Range{
	LL l,r;
}range[maxn];
LL n,q,ret;
LL a[maxn],lt[maxn],rt[maxn],pos[maxn],rd[maxn],ld[maxn];
LL ls[maxn][2],rs[maxn][2];
void Init(){
	n=Read(); q=Read();
	for(LL i=1;i<=n;++i) a[i]=Read();
	for(LL i=1;i<=q;++i){
		LL l(Read()),r(Read());
		range[i]=(Range){l,r};
	}
}
void Fir(){
	for(LL i=1;i<=n;++i) pos[a[i]]=i;
	for(LL i=1;i<=n;++i) rd[i]=i,ld[i]=i;
	for(LL i=1;i<=n;++i){
		ls[i][0]=ls[i][1]=0;
		rs[i][0]=rs[i][1]=0;
	}
}
void Modify(LL l,LL r){
	LL lt,rt;
	lt=l;
	while(lt<r){
		rt=rd[lt];
		Chkmin(rt,r);
		for(LL i=lt;i<=rt;++i){
			if(rd[i]<r){
				for(LL j=rd[i]+1;j<=r;++j){
					if(a[j]<a[i]){
						LL &x(rs[i][0]);
						if(!x || (x && a[x]<a[j])){
							ret-=ls[x][1]==i;
							x=j;
							ret+=ls[x][1]==i;
						}
					}else{
						LL &x(rs[i][1]);
						if(!x || (x && a[x]>a[j])){
							ret-=ls[x][0]==i;
							x=j;
							ret+=ls[x][0]==i;
						}
					}
				}
				rd[i]=r;
			}else break;
		}
		lt=rt+1;
	}
	rt=r;
	while(rt>l){
		lt=ld[rt];
		Chkmax(lt,l);
		for(LL i=rt;i>=lt;--i){
			if(ld[i]>l){
				for(LL j=l;j<=ld[i]-1;++j){
					if(a[j]<a[i]){
						LL &x(ls[i][0]);
						if(!x || (x && a[x]<a[j])){
							ret-=rs[x][1]==i;
							x=j;
							ret+=rs[x][1]==i;
						}
					}else{
						LL &x(ls[i][1]);
						if(!x || (x && a[x]>a[j])){
							ret-=rs[x][0]==i;
							x=j;
							ret+=rs[x][0]==i;
						}
					}
				}
				ld[i]=l;
			}else break;
		}
		rt=lt-1;
	}
}
void Solve(){
	for(LL ti=1;ti<=q;++ti){
		LL l(range[ti].l),r(range[ti].r);
		Modify(l,r);
		printf("%d\n",ret);
	}
}
int main(){
	Init();
	Fir();
	Solve();
	return 0;
}




### Prompt

Develop a solution in cpp 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>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
#define pii std::pair<LL,LL>
const LL maxn=1e6+9,mod=998244353,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
LL add(LL x,LL y){
	return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
	}return ret;
}
struct Range{
	LL l,r;
}range[maxn];
LL n,q,ret;
LL a[maxn],lt[maxn],rt[maxn],pos[maxn],rd[maxn],ld[maxn];
LL ls[maxn][2],rs[maxn][2];
void Init(){
	n=Read(); q=Read();
	for(LL i=1;i<=n;++i) a[i]=Read();
	for(LL i=1;i<=q;++i){
		LL l(Read()),r(Read());
		range[i]=(Range){l,r};
	}
}
void Fir(){
	for(LL i=1;i<=n;++i) pos[a[i]]=i;
	for(LL i=1;i<=n;++i) rd[i]=i,ld[i]=i;
	for(LL i=1;i<=n;++i){
		ls[i][0]=ls[i][1]=0;
		rs[i][0]=rs[i][1]=0;
	}
}
void Modify(LL l,LL r){
	LL lt,rt;
	lt=l;
	while(lt<r){
		rt=rd[lt];
		Chkmin(rt,r);
		for(LL i=lt;i<=rt;++i){
			if(rd[i]<r){
				for(LL j=rd[i]+1;j<=r;++j){
					if(a[j]<a[i]){
						LL &x(rs[i][0]);
						if(!x || (x && a[x]<a[j])){
							ret-=ls[x][1]==i;
							x=j;
							ret+=ls[x][1]==i;
						}
					}else{
						LL &x(rs[i][1]);
						if(!x || (x && a[x]>a[j])){
							ret-=ls[x][0]==i;
							x=j;
							ret+=ls[x][0]==i;
						}
					}
				}
				rd[i]=r;
			}else break;
		}
		lt=rt+1;
	}
	rt=r;
	while(rt>l){
		lt=ld[rt];
		Chkmax(lt,l);
		for(LL i=rt;i>=lt;--i){
			if(ld[i]>l){
				for(LL j=l;j<=ld[i]-1;++j){
					if(a[j]<a[i]){
						LL &x(ls[i][0]);
						if(!x || (x && a[x]<a[j])){
							ret-=rs[x][1]==i;
							x=j;
							ret+=rs[x][1]==i;
						}
					}else{
						LL &x(ls[i][1]);
						if(!x || (x && a[x]>a[j])){
							ret-=rs[x][0]==i;
							x=j;
							ret+=rs[x][0]==i;
						}
					}
				}
				ld[i]=l;
			}else break;
		}
		rt=lt-1;
	}
}
void Solve(){
	for(LL ti=1;ti<=q;++ti){
		LL l(range[ti].l),r(range[ti].r);
		Modify(l,r);
		printf("%d\n",ret);
	}
}
int main(){
	Init();
	Fir();
	Solve();
	return 0;
}




```