#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ss second
const int N = 8e6 + 5;
int bit[N];
int a[N];
void update (int idx, int val) {
while(idx < N) {
bit[idx] += val;
idx += idx & -idx;
}
}
int get (int idx) {
if (idx<=0) {
return 0;
}
int s = 0;
while (idx > 0){
s += bit[idx];
idx -= idx& -idx;
}
return s;
}
signed main() {
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
update(i, a[i]);
}
while (q--) {
int l, r;
cin >> l >> r;
int L = 0;
int R = (r - l + 1);
while (L + 1 < R) {
int mid = (L + R + 1) / 2;
if ( get(R) - get(L + 1) > mid ) {
L = mid;
}
else {
R = mid;
}
}
cout << " * "<< L << endl;
}
return 0;
}
