#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		int sum=0;
		stack<int> stk;
		for(int j=x;j<=y;j++){
			if(!stk.size()||a[j]<stk.top()){
				stk.push(a[j]);
			}
			else{
//				cout<<"111"<<stk.top()<<" "<<a[j]<<"\n";
				while(stk.size()&&stk.top()<a[j]){
//					cout<<"!!!";
					stk.pop();
					sum++;
				}
//			stk.push(a[j]);			
			}		



		}
		cout<<sum<<" "<<stk.size()<<"\n";
		cout<<sum+stk.size()<<"\n";
	}
	return 0;
}