// Author -- xyr2005

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-(x)))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return !b?a:gcd(b,a%b);}
template <typename _Tp>inline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>inline void chmax(_Tp &a,const _Tp &b){a=a<b?b:a;}
template <typename _Tp>inline void chmin(_Tp &a,const _Tp &b){a=a<b?a:b;}
template <typename _Tp>inline void read(_Tp &x){
	char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	f&&(x=-x);
}
template <typename _Tp,typename... Args>void read(_Tp &t,Args &...args){read(t);read(args...);}
inline int read_str(char *s){
	char ch(getchar());while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;*tar++=ch,ch=getchar();while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *tar++=ch,ch=getchar();
	return *tar=0,tar-s;
}

const int N=25005;
int L[N],R[N],a[N],rev[N];
int p1[N],p2[N],s1[N],s2[N];
int main(){
	int n,q;read(n,q);
	for(int i=1;i<=n;++i)read(a[i]),rev[a[i]]=i;
	int l,r,ans=0;
	for(int i=1;i<=n;++i)L[i]=R[i]=i;
	a[0]=inf,s2[0]=p2[0]=inf;
	while(q--){
		read(l,r);
		for(int i=r;i>=l&&L[i]>l;--i){
			ans-=s2[p1[i]]<=a[i];
			while(L[i]>l){
				int o=--L[i];
				if(a[o]>a[i])p1[i]=a[o]<a[p1[i]]?o:p1[i];
				else{
					if(a[o]>p2[i]){
						for(int j=p2[i];j<a[o];++j)ans-=s1[rev[j]]==i;
						p2[i]=a[o];
					}
				}
			}
			ans+=s2[p1[i]]<=a[i];
		}
		for(int i=l;i<=r&&R[i]<r;++i){
			ans-=p2[s1[i]]<=a[i];
			while(R[i]<r){
				int o=++R[i];
				if(a[o]>a[i])s1[i]=a[o]<a[s1[i]]?o:s1[i];
				else{
					if(a[o]>s2[i]){
						for(int j=s2[i];j<a[o];++j)ans-=p1[rev[j]]==i;
						s2[i]=a[o];
					}
				}
			}
			ans+=p2[s1[i]]<=a[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 -- xyr2005

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-(x)))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return !b?a:gcd(b,a%b);}
template <typename _Tp>inline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>inline void chmax(_Tp &a,const _Tp &b){a=a<b?b:a;}
template <typename _Tp>inline void chmin(_Tp &a,const _Tp &b){a=a<b?a:b;}
template <typename _Tp>inline void read(_Tp &x){
	char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	f&&(x=-x);
}
template <typename _Tp,typename... Args>void read(_Tp &t,Args &...args){read(t);read(args...);}
inline int read_str(char *s){
	char ch(getchar());while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;*tar++=ch,ch=getchar();while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *tar++=ch,ch=getchar();
	return *tar=0,tar-s;
}

const int N=25005;
int L[N],R[N],a[N],rev[N];
int p1[N],p2[N],s1[N],s2[N];
int main(){
	int n,q;read(n,q);
	for(int i=1;i<=n;++i)read(a[i]),rev[a[i]]=i;
	int l,r,ans=0;
	for(int i=1;i<=n;++i)L[i]=R[i]=i;
	a[0]=inf,s2[0]=p2[0]=inf;
	while(q--){
		read(l,r);
		for(int i=r;i>=l&&L[i]>l;--i){
			ans-=s2[p1[i]]<=a[i];
			while(L[i]>l){
				int o=--L[i];
				if(a[o]>a[i])p1[i]=a[o]<a[p1[i]]?o:p1[i];
				else{
					if(a[o]>p2[i]){
						for(int j=p2[i];j<a[o];++j)ans-=s1[rev[j]]==i;
						p2[i]=a[o];
					}
				}
			}
			ans+=s2[p1[i]]<=a[i];
		}
		for(int i=l;i<=r&&R[i]<r;++i){
			ans-=p2[s1[i]]<=a[i];
			while(R[i]<r){
				int o=++R[i];
				if(a[o]>a[i])s1[i]=a[o]<a[s1[i]]?o:s1[i];
				else{
					if(a[o]>s2[i]){
						for(int j=s2[i];j<a[o];++j)ans-=p1[rev[j]]==i;
						s2[i]=a[o];
					}
				}
			}
			ans+=p2[s1[i]]<=a[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

```