手玩样例发现，如果查询的数\(k\)在区间外，那么结果一定是\(-1\)。
我们设数字\(k\)在数组中的下标为\(idx_k\)。
如果在区间里面呢，我们由题意可以知道，题中的二分方式是按照数列单调递增的特性进行二分的，那么我们肯定需要让二分找到\(k\)的路径上的所有的点的值与\(k\)的关系都是满足单调性的，即如果\(i<idx_k\)，那么有\(p_i<k\)，这样我们可以通过二分找到。
这个二分的路径是唯一的，因为如果不唯一那就说明我们在某一处选择另一半的区间进行二分，但是这个区间显然是不会包含\(k\)的，所以说路径一定是唯一的。那么我们就可以通过模拟二分，然后找出二分的路径，如果路径内部可以自我消化满足二分的条件，即所有形如\(i<idx_k,p_i>k\)或\(i>idx_k,p_i<k\)的数可以通过重新排列满足条件，那么就可以。否则，我们需要额外的选择路径之外的数参与交换。
代码
#include <bits/stdc++.h>
using namespace std;
/**/
void sol() {int n,q;cin>>n>>q;vector<int> p(n+1,0),idx(n+1,0);for(int i=1;i<=n;i++){cin>>p[i];idx[p[i]]=i;}while(q--){int lt,rt,k;cin>>lt>>rt>>k;if(idx[k]<lt||idx[k]>rt) cout<<"-1 ";else{int low=0,high=0,numlow,numhigh;numlow=numhigh=0;int remlow=k-1,remhigh=n-k;int l=lt,r=rt,mid;while(l<=r){mid=(l+r)>>1;if(p[mid]==k) break; else if(mid<idx[k]){l=mid+1;if(p[mid]>k){low++;numhigh++;}else remlow--;}else{r=mid-1;if(p[mid]<k){high++;numlow++;}else remhigh--;}}if(low>remlow||high>remhigh) cout<<"-1 ";else{int extra=0;extra+=max(low-numlow,0);extra+=max(high-numhigh,0);cout<<low+high+extra<<" ";}}}cout<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
总结：二分查找一个数时的路径是唯一的。