// Author: gsczl71
// Copyright (c) 2024 gsczl71 All rights reserved.

#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define endl '\n'
#define debug puts("AK IOI")
#define re register
#define pb push_back
#define mem(a,x) memset((a),(x),sizeof(a))
#define vi vector<int>
#define pq priority_queue
using namespace std;
//#define int long long
const int mod = 1e9+7;
//const int mod = 998244353;
const int inf = 0x3f3f3f3f,N = 2e5+5,M = 1e6+5,K = 3000+5;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n,q;
int a[N];
struct node{
	int x,y,id;
} que[N];
int id[N],len ;
void init(){
	len = sqrt(n);
	for(int i = 1;i <= n;i++ ){
		id[i] = ((i - 1) / len) + 1;
	}
}
bool cmp(node a,node b){
	if(id[a.x] == id[b.x]){
		return a.y < b.y;
	}else{
		return id[a.x] < id[b.x];
	}
} 
vector<int> gen[N];
int cnt[N];
int cnt2[N]; 
int maxn;
int res;
void add(int x){
	cnt[x] += que[x].id * a[que[x].id];
	maxn = max(maxn,cnt[x]);
}
int ans[N];
void solve(){
	cin >> n >> q;
	init();
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= q;i++) cin >> que[i].x >> que[i].y;
	for(int i = 1;i <= q;i++) que[i].id = i ;
	for(int i = 1;i <= q;i++) gen[id[que[i].x]].pb(i);
	sort(que+1,que+1+q,cmp);
	for(int i = 1; i <= n/len;i++){
		memset(cnt ,0,sizeof cnt);
		maxn=0;
		int l = i * len + 1;
		int r = i * len;
		
		for(auto it:gen[i]){
			while(que[it].y > r)add(++r);
			int tmpl = l;
			res=maxn;
			while(que[it].x < l){
				l--;
				cnt2[l] += que[l].id*a[que[l].id];
				res = max(res,cnt[l] + cnt2[l]);
			}ans[it]=res;
			while(l < tmpl){
				cnt2[l] -= que[l].id*a[que[l].id];
				l++;
			}//回溯
		}
	}for(int i = 1;i <= q;i++) cout<<ans[i]<<endl;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	while(T--) solve();
	return 0;
}