拜谢，rt

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
// const long long char_z=0;
//ios::sync_with_stdio(0);cin.tie(),cout.tie();
ll k[100005];int m,n,p;ll a,b,c,ans=0;
int pos[100007]/*判断点属于哪一个块*/;
ll maxn=0,max_num[100000];
int line_l[100007],line_r[100007];
inline long long read()
{
	char cc=getchar();long long f=1,ans=0;
	while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();}return f*ans;
}
inline void reads(){n=read();m=read();for(int i=1;i<=n;i++)k[i]=read();}
inline void build()
{
	int t=sqrt(n);//块的个数 
	for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界 
	if(line_r[t]<=n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整 
	for(int i=1;i<=t;i++)//初始化区间加值和这个点属于那个块
	for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;} 
	for(int i=1;i<=t;i++){maxn=0;for(int j=line_l[i];j<=line_r[i];j++){maxn=max(k[j],maxn);}max_num[i]=maxn;}
}
inline void ask_line()
{
	a=read();b=read();ans=0;
	if(pos[a]==pos[b]){printf("%lld\n",max_num[pos[a]]);return ;}
	for(int i=pos[a]+1;i<=pos[b]-1;i++)ans=max(ans,max_num[i]);
	for(int i=a;i<=line_r[pos[a]];i++)ans=max(ans,k[i]);
	for(int i=line_l[pos[b]];i<=b;i++)ans=max(ans,k[i]);
//	for(int i=a;i<=line_r[pos[a]];i++)ans+=k[i];for(int i=line_l[pos[b]];i<=b;i++)ans+=k[i];
	printf("%lld\n",ans);return ;
}
inline void main_d() {reads();build();for(int i=1;i<=m;i++)ask_line();}
int main(){main_d();return 0;}