We don't even need to build the permutation tree for this question. We will use the $$$Q$$$ array described earlier. Every time we insert a new value, we just need to count the number of values which are set to 0.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	ll val=0,lazy=0,num;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		num=e-s+1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			
			val=min(l->val,r->val);
			num=(l->val==val?l->num:0)+(r->val==val?r->num:0);
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j){
			if (val==0) return num;
			else return 0;
		}
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return l->query(i,m)+r->query(m+1,j);
	}
}*root=new node(0,300005);

int n;
int arr[300005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n){
		int a,b;
		cin>>a>>b;
		arr[a-1]=b;
	}
	
	vector<int> mx={-1},mn={-1};
	ll ans=0;
	
	rep(x,0,n){
		while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
			int temp=mx.back();
			mx.pop_back();
			root->update(mx.back()+1,temp,arr[x]-arr[temp]);
		}
		mx.push_back(x);
		
		while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
			int temp=mn.back();
			mn.pop_back();
			root->update(mn.back()+1,temp,arr[temp]-arr[x]);
		}
		mn.push_back(x);
		
		ans+=root->query(0,x);
		
		root->update(0,x,-1);
	}
	
	cout<<ans<<endl;
}

We build the permutation tree and do 2k decomp on the nodes. For each query, we go to a arbitrary node that is contained in the query then using binary lifting, jump to the lowest node that contains the given query. This can also be done by finding the LCA of the left and right endpoints.

Furthermore, when the lowest node that contains the given query is a join node, we still need to binary search again to remove as many left and right endpoints to get the smallest interval.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	ll val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=min(l->val,r->val);
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
};

int n,q;
int arr[100005];
ii range[200005];
ii span[200005];
vector<int> children[200005];
int parent[200005];
int typ[200005];
int idx; //new index to assign to nodes

ii get_range(ii i,ii j){
	return ii(min(i.fi,j.fi),max(i.se,j.se));
}

void add_edge(int u,int v){ //u is parent of v
	parent[v]=u;
	children[u].push_back(v);
}

bool adj(int i,int j){
	return range[i].se==range[j].fi-1;
}

int length(int i){
	return range[i].se-range[i].fi+1;
}

void build(){
	idx=n;
	memset(parent,-1,sizeof(parent));
	
	node *root=new node(0,100005);
	vector<int> mx={-1},mn={-1}; //stacks for max and min
	
	vector<int> nodes; //stack of cut and join nodes
	
	rep(x,0,n){
		//update Q values
		while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
			int temp=mx.back();
			mx.pop_back();
			root->update(mx.back()+1,temp,arr[x]-arr[temp]);
		}
		mx.push_back(x);
		
		while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
			int temp=mn.back();
			mn.pop_back();
			root->update(mn.back()+1,temp,arr[temp]-arr[x]);
		}
		mn.push_back(x);
		
		//handle stack updates
		range[x]=ii(arr[x],arr[x]);
		span[x]=ii(x,x);
		int curr=x;
		
		while (true){
			if (!nodes.empty() && (adj(nodes.back(),curr) || adj(curr,nodes.back()))){
				if ((adj(nodes.back(),curr) && typ[nodes.back()]==1)||
				  (adj(curr,nodes.back()) && typ[nodes.back()]==2)){
					add_edge(nodes.back(),curr);
					
					range[nodes.back()]=get_range(range[nodes.back()],range[curr]);
					span[nodes.back()]=get_range(span[nodes.back()],span[curr]);
					
					curr=nodes.back();
					nodes.pop_back();
				}
				else{ //make a new join node
					typ[idx]=(adj(nodes.back(),curr) ? 1:2);
					add_edge(idx,nodes.back());
					add_edge(idx,curr);
					
					range[idx]=get_range(range[nodes.back()],range[curr]);
					span[idx]=get_range(span[nodes.back()],span[curr]);
					
					nodes.pop_back();
					curr=idx++;
				}
			}
			else if (x-(length(curr)-1) && root->query(0,x-length(curr))==0){
				int len=length(curr);
				ii r=range[curr];
				ii s=span[curr];
				
				add_edge(idx,curr);
				
				do{
					len+=length(nodes.back());
					r=get_range(r,range[nodes.back()]);
					s=get_range(s,span[nodes.back()]);
					
					add_edge(idx,nodes.back());
					
					nodes.pop_back();
				} while (r.se-r.fi+1!=len);
				
				reverse(all(children[idx]));
				range[idx]=r;
				span[idx]=s;
				curr=idx++;
			}
			else{
				break;
			}
		}
		
		nodes.push_back(curr);
		root->update(0,x,-1);
	}
}

int tkd[200005][20];

void dfs(int i){
	for (auto &it:children[i]){
		int curr=tkd[it][0]=i;
		for (int x=0;curr!=-1;x++){
			curr=tkd[it][x+1]=tkd[curr][x];
		}
		
		dfs(it);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x];
	
	build();
	
	memset(tkd,-1,sizeof(tkd));
	rep(x,0,idx){
		if (parent[x]==-1) dfs(x);
	}
	
	cin>>q;
	int a,b;
	while (q--){
		cin>>a>>b;
		
		if (a==b){
			cout<<a<<" "<<b<<endl;
			continue;
		}
		
		a--,b--;
		int curr=a;
		
		rep(x,20,0){
			if (tkd[curr][x]!=-1 && span[tkd[curr][x]].se<b) curr=tkd[curr][x];
		}
		
		curr=tkd[curr][0];
		if (typ[curr]==0) cout<<span[curr].fi+1<<" "<<span[curr].se+1<<endl;
		else{
			int lo=-1,hi=sz(children[curr]);
			
			rep(x,20,0){
				if (lo+(1<<x)<sz(children[curr]) && span[children[curr][lo+(1<<x)]].se<a) lo+=(1<<x);
				if (0<=hi-(1<<x) && b<span[children[curr][hi-(1<<x)]].fi) hi-=(1<<x);
			}
			
			cout<<span[children[curr][lo+1]].fi+1<<" "<<span[children[curr][hi-1]].se+1<<endl;
		}
	}
	
}