#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<pii, pii> p4i;
const int MXN = 205;
int n, q, ql[MXN], qr[MXN], qt[MXN], ans[MXN];
vector<int> a, b;
vector<pii> op;
void MOVE() {
for (int i = 1; i <= n; i++) b[i] = max(a[i - 1], a[i]);
swap(a, b);
}
int QUERY(int l, int r) {
int ans = 0;
for (int i = l; i <= r; i++) ans += a[i];
return ans;
}
void miku() {
cin >> n >> q;
a.resize(n + 1);
b.resize(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) op.push_back(mp(i, -1LL));
for (int i = 1; i <= q; i++) {
cin >> qt[i] >> ql[i] >> qr[i];
op.push_back(mp(qt[i], i));
}
sort(op.begin(), op.end());
for (auto &i : op) {
if (i.sc == -1) {
MOVE();
// for (int j = 1; j <= n; j++) cout << a[j] << ' ';
// cout << endl;
} else ans[i.sc] = QUERY(ql[i.sc], qr[i.sc]);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
miku();
return 0;
}
