//Mobius_Treap
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> II;
typedef vector< II > VII;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef long long int LL;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
//#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
const int N=100100;
int K,A[N];
pair<II,II> qu[N];
deque<int> Q[N];
multiset<int > my;
int ans[N];
bool cmp(pair<II,II> a,pair<II,II> b)
{
int aa=a.S.S;
int bb=b.S.S;
if(aa!=bb)
return (aa<bb);
return a.F.F<b.F.F;
}
int main()
{
int n,q;
si(n);
si(q);
K=sqrt(2*N);
A[0]=50050;
for(int i=1;i<=n;i++)
{
int x;
si(x);
A[i]=A[i-1]+x;
trace(i,A[i]);
}
for(int i=0;i<q;i++)
{
si(qu[i].F.F),si(qu[i].F.S);
qu[i].F.F--;
qu[i].S.F=i;
qu[i].S.S=qu[i].F.S/K;
}
sort(qu,qu+q,cmp);
int l=0,r=0;
Q[A[0]].push_front(0);
for(int i=0;i<q;i++)
{
int L=qu[i].F.F;
int R=qu[i].F.S;
while(r<R)
{
r++;
if(SZ(Q[A[r]])>1)
{
int prev=Q[A[r]].back()-Q[A[r]].front();
my.erase(my.find(prev));
}
Q[A[r]].push_back(r);
if(SZ(Q[A[r]])>1)
{
int cur=Q[A[r]].back()-Q[A[r]].front();
my.insert(cur);
}
}
while(l>L)
{
l--;
if(SZ(Q[A[l]])>1)
{
int prev=Q[A[l]].back()-Q[A[l]].front();
my.erase(my.find(prev));
}
Q[A[l]].push_front(l);
if(SZ(Q[A[l]])>1)
{
int cur=Q[A[l]].back()-Q[A[l]].front();
my.insert(cur);
}
}
while(l<L)
{
if(SZ(Q[A[l]])>1)
{
int prev=Q[A[l]].back()-Q[A[l]].front();
my.erase(my.find(prev));
}
Q[A[l]].pop_front();
if(SZ(Q[A[l]])>1)
{
int cur=Q[A[l]].back()-Q[A[l]].front();
my.insert(cur);
}
l++;
}
while(r>R)
{
if(SZ(Q[A[r]])>1)
{
int prev=Q[A[r]].back()-Q[A[r]].front();
my.erase(my.find(prev));
}
Q[A[r]].pop_back();
if(SZ(Q[A[r]])>1)
{
int cur=Q[A[r]].back()-Q[A[r]].front();
my.insert(cur);
}
r--;
}
if(!my.empty())
ans[qu[i].S.F]=*my.rbegin();
}
for(int i=0;i<q;i++)
dout(ans[i]);
return 0;
}
Ly9Nb2JpdXNfVHJlYXAKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LGludD4gICBJSTsKdHlwZWRlZiB2ZWN0b3I8IElJID4gICAgICBWSUk7CnR5cGVkZWYgdmVjdG9yPGludD4gICAgIFZJOwp0eXBlZGVmIHZlY3RvcjwgVkkgPiAJVlZJOwp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgCUxMOwoKI2RlZmluZSBQQiBwdXNoX2JhY2sKI2RlZmluZSBNUCBtYWtlX3BhaXIKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBTWihhKSAoaW50KShhLnNpemUoKSkKI2RlZmluZSBBTEwoYSkgYS5iZWdpbigpLGEuZW5kKCkKI2RlZmluZSBTRVQoYSxiKSBtZW1zZXQoYSxiLHNpemVvZihhKSkKCiNkZWZpbmUgc2kobikgc2NhbmYoIiVkIiwmbikKI2RlZmluZSBkb3V0KG4pIHByaW50ZigiJWRcbiIsbikKI2RlZmluZSBzbGwobikgc2NhbmYoIiVsbGQiLCZuKQojZGVmaW5lIGxsZG91dChuKSBwcmludGYoIiVsbGRcbiIsbikKI2RlZmluZSBmYXN0X2lvIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCkKCi8vI2RlZmluZSBUUkFDRQoKI2lmZGVmIFRSQUNFCiNkZWZpbmUgdHJhY2UoLi4uKSBfX2YoI19fVkFfQVJHU19fLCBfX1ZBX0FSR1NfXykKdGVtcGxhdGUgPHR5cGVuYW1lIEFyZzE+CnZvaWQgX19mKGNvbnN0IGNoYXIqIG5hbWUsIEFyZzEmJiBhcmcxKXsKCWNlcnIgPDwgbmFtZSA8PCAiIDogIiA8PCBhcmcxIDw8IHN0ZDo6ZW5kbDsKfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMSwgdHlwZW5hbWUuLi4gQXJncz4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZXMsIEFyZzEmJiBhcmcxLCBBcmdzJiYuLi4gYXJncyl7Cgljb25zdCBjaGFyKiBjb21tYSA9IHN0cmNocihuYW1lcyArIDEsICcsJyk7Y2Vyci53cml0ZShuYW1lcywgY29tbWEgLSBuYW1lcykgPDwgIiA6ICIgPDwgYXJnMTw8IiB8ICI7X19mKGNvbW1hKzEsIGFyZ3MuLi4pOwp9CiNlbHNlCiNkZWZpbmUgdHJhY2UoLi4uKQojZW5kaWYKCi8vRklMRSAqZmluID0gZnJlb3BlbigiaW4iLCJyIixzdGRpbik7Ci8vRklMRSAqZm91dCA9IGZyZW9wZW4oIm91dCIsInciLHN0ZG91dCk7Cgpjb25zdCBpbnQgTj0xMDAxMDA7CmludCBLLEFbTl07CnBhaXI8SUksSUk+IHF1W05dOwpkZXF1ZTxpbnQ+IFFbTl07Cm11bHRpc2V0PGludCA+IG15OwppbnQgYW5zW05dOwpib29sIGNtcChwYWlyPElJLElJPiBhLHBhaXI8SUksSUk+IGIpCnsKCWludCBhYT1hLlMuUzsKCWludCBiYj1iLlMuUzsKCWlmKGFhIT1iYikKCQlyZXR1cm4gKGFhPGJiKTsKCXJldHVybiBhLkYuRjxiLkYuRjsKfQppbnQgbWFpbigpCnsKCWludCBuLHE7CglzaShuKTsKCXNpKHEpOwoJSz1zcXJ0KDIqTik7CglBWzBdPTUwMDUwOwoJZm9yKGludCBpPTE7aTw9bjtpKyspCgl7CgkJaW50IHg7CgkJc2koeCk7CgkJQVtpXT1BW2ktMV0reDsKCQl0cmFjZShpLEFbaV0pOwoJfQoJZm9yKGludCBpPTA7aTxxO2krKykKCXsKCQlzaShxdVtpXS5GLkYpLHNpKHF1W2ldLkYuUyk7CgkJcXVbaV0uRi5GLS07CgkJcXVbaV0uUy5GPWk7CgkJcXVbaV0uUy5TPXF1W2ldLkYuUy9LOwoJfQoJc29ydChxdSxxdStxLGNtcCk7CglpbnQgbD0wLHI9MDsKCVFbQVswXV0ucHVzaF9mcm9udCgwKTsKCWZvcihpbnQgaT0wO2k8cTtpKyspCgl7CgkJaW50IEw9cXVbaV0uRi5GOwoJCWludCBSPXF1W2ldLkYuUzsKCQl3aGlsZShyPFIpCgkJewoJCQlyKys7CgkJCWlmKFNaKFFbQVtyXV0pPjEpCgkJCXsKCQkJCWludCBwcmV2PVFbQVtyXV0uYmFjaygpLVFbQVtyXV0uZnJvbnQoKTsKCQkJCW15LmVyYXNlKG15LmZpbmQocHJldikpOwoJCQl9CgkJCVFbQVtyXV0ucHVzaF9iYWNrKHIpOwoJCQlpZihTWihRW0Fbcl1dKT4xKQoJCQl7CgkJCQlpbnQgY3VyPVFbQVtyXV0uYmFjaygpLVFbQVtyXV0uZnJvbnQoKTsKCQkJCW15Lmluc2VydChjdXIpOwoJCQl9CgkJfQoJCXdoaWxlKGw+TCkKCQl7CgkJCWwtLTsKCQkJaWYoU1ooUVtBW2xdXSk+MSkKCQkJewoJCQkJaW50IHByZXY9UVtBW2xdXS5iYWNrKCktUVtBW2xdXS5mcm9udCgpOwoJCQkJbXkuZXJhc2UobXkuZmluZChwcmV2KSk7CgkJCX0KCQkJUVtBW2xdXS5wdXNoX2Zyb250KGwpOwoJCQlpZihTWihRW0FbbF1dKT4xKQoJCQl7CgkJCQlpbnQgY3VyPVFbQVtsXV0uYmFjaygpLVFbQVtsXV0uZnJvbnQoKTsKCQkJCW15Lmluc2VydChjdXIpOwoJCQl9CgkJfQoJCXdoaWxlKGw8TCkKCQl7CgkJCWlmKFNaKFFbQVtsXV0pPjEpCgkJCXsKCQkJCWludCBwcmV2PVFbQVtsXV0uYmFjaygpLVFbQVtsXV0uZnJvbnQoKTsKCQkJCW15LmVyYXNlKG15LmZpbmQocHJldikpOwoJCQl9CgkJCVFbQVtsXV0ucG9wX2Zyb250KCk7CgkJCWlmKFNaKFFbQVtsXV0pPjEpCgkJCXsKCQkJCWludCBjdXI9UVtBW2xdXS5iYWNrKCktUVtBW2xdXS5mcm9udCgpOwoJCQkJbXkuaW5zZXJ0KGN1cik7CgkJCX0KCQkJbCsrOwoJCX0KCQl3aGlsZShyPlIpCgkJewoJCQlpZihTWihRW0Fbcl1dKT4xKQoJCQl7CgkJCQlpbnQgcHJldj1RW0Fbcl1dLmJhY2soKS1RW0Fbcl1dLmZyb250KCk7CgkJCQlteS5lcmFzZShteS5maW5kKHByZXYpKTsKCQkJfQoJCQlRW0Fbcl1dLnBvcF9iYWNrKCk7CgkJCWlmKFNaKFFbQVtyXV0pPjEpCgkJCXsKCQkJCWludCBjdXI9UVtBW3JdXS5iYWNrKCktUVtBW3JdXS5mcm9udCgpOwoJCQkJbXkuaW5zZXJ0KGN1cik7CgkJCX0KCQkJci0tOwoJCX0KCQlpZighbXkuZW1wdHkoKSkKCQkJYW5zW3F1W2ldLlMuRl09Km15LnJiZWdpbigpOwoJfQoJZm9yKGludCBpPTA7aTxxO2krKykKCQlkb3V0KGFuc1tpXSk7CglyZXR1cm4gMDsKfQ==