rt，49 TLE

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long dp[100005][28];
long long lg[100005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>dp[i][0];
	}
	for(int j=1;j<=16;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int l,r,s;
		cin>>l>>r;
		s=__lg(r-l+1);
		cout<<max(dp[l][s],dp[r-(1<<s)+1][s])<<endl;
	}
}