铁路旅行

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,K,q,a[N],stk[N],l[20][N],r[20][N];
int main(){
	cin>>n>>K>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	int tp=0;
	for(int i=1;i<=n;i++){
		while(tp&&a[i]>a[stk[tp]])tp--;
		l[0][i]=tp?stk[tp]:i;
		stk[++tp]=i;
	}
	tp=0;
	for(int i=n;i;i--){
		while(tp&&a[i]>a[stk[tp]])tp--;
		r[0][i]=tp?stk[tp]:i;
		stk[++tp]=i;
	}
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++){
			l[i][j]=min(l[i-1][l[i-1][j]],l[i-1][r[i-1][j]]);
			r[i][j]=max(r[i-1][r[i-1][j]],r[i-1][l[i-1][j]]);
		}
	for(int x,y;q--;){
		cin>>x>>y;
		if(x>y)swap(x,y);
		int s=x,t=x,ans=0;
		for(int i=18;~i;i--){
			int ns=min(l[i][s],l[i][t]),nt=max(r[i][s],r[i][t]);
			if(nt<y)s=ns,t=nt,ans+=1<<i;
		}
		int p=t;
		s=t=y;cerr<<p<<ans;//<-
		for(int i=18;~i;i--){
			int ns=min(l[i][s],l[i][t]),nt=max(r[i][s],r[i][t]);
			if(ns>p)s=ns,t=nt,ans+=1<<i;
		}
		cerr<<s;//<-
		cout<<ans<<'\n';
	}
}

数据：

7 3 1
3
1
2
2
2
1
3
2 6

cerr输出315,输出答案2

这应该是说它得经过3,5俩个点吧

但最优方案显然是a2->a1->a7->a6（答案没问题，但路径怎么回事？）求助。