Shared code

//#pragma comment(linker, "/stack:336777216")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
inline char gc() {
	static char buf[1 << 16];
	static size_t bc, be;
	if (bc >= be) {
		buf[0] = 0, bc = 0;
		be = fread(buf, 1, sizeof(buf), stdin);
	}
	return buf[bc++];
}
 
int readInt() {
	int a, c;
	while ((a = gc()) < 40);
	if (a == '-') return -readInt();
	while ((c = gc()) >= 48) a = a * 10 + c - 480;
	return a - 48;
}
 
typedef long long ll;
const int INF = 1000000007;
 
template<class T>
struct RMQ2 {
	vector<vector<T>> jmp;
	RMQ2(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};
 
struct RMQ{
	vector<int> s; 
	RMQ2<int> rmq;
 
	RMQ(int n = 0) : s(n, INF), rmq(s) {}
	void update(int pos, ll val) {
		s[pos] = val;
	}
	void init() {
		rmq = RMQ2(s);
	}
	int query(int b, int e) {
		return rmq.query(b, e);	
	}
};
 
struct RSQ{
	vector<ll> s;
	RSQ(int n = 0) : s(n) {}
	void update(int pos, ll val) {
		s[pos] = val;
	}
	void init() {
		for (int i = 1; i < s.size(); i++) {
			s[i] += s[i-1];
		}
	}
	ll query(int b, int e) {
		if (b == 0) return s[e-1];
		else return s[e-1] - s[b-1];	
	}
};
 
int most_significant_bit(int x) {
	for (int i = 29; i >= 0; i--) {
		if (x & (1 << i)) return i;
	}
	return -1;
}
 
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
 
	int n = readInt(), q = readInt();
	vector<RMQ> rmq(30, RMQ(n));
	vector<RSQ> rsq(30, RSQ(n));
	for (int i = 0; i < n; i++) {
		int x = readInt();
		int ms = most_significant_bit(x);
 
		rmq[ms].update(i, x);
		rsq[ms].update(i, x);
	}
	for (int i = 0; i < 30; i++) {
		rsq[i].init(); rmq[i].init();
	}
 
	while (q--) {
		int l = readInt(), r = readInt();
		l--;
		if (rmq[0].query(l, r) != 1) {
			cout << "1\n"; continue;
		}
 
		ll sum = rsq[0].query(l, r);
		for (int i = 1; i < 30; i++) {
			int cand = rmq[i].query(l, r);
			if (cand != INF && cand > sum+1) break;
 
			sum += rsq[i].query(l, r);
		}
		cout << sum+1 << '\n';
	}
 
	return 0;
}