#include <bits/extc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

mt19937 rnd(57);

struct Node {
    long long x;
    int y;
    long long val, mn, mx;
    Node *l, *r;

    Node(long long _x, long long _val) {
        x = _x;
        val = _val;
        y = rnd();
        mn = mx = val;
        l = r = nullptr;
    }
};

long long mn(Node *root) {
    if (root == nullptr) {
        return inf;
    }
    return root->mn;
}

long long mx(Node *root) {
    if (root == nullptr) {
        return -inf;
    }
    return root->mx;
}

void relax(Node *root) {
    root->mn = min(min(mn(root->l), mn(root->r)), root->val);
    root->mx = max(max(mx(root->l), mx(root->r)), root->val);
}

Node *merge(Node *root1, Node *root2) {
    if (root1 == nullptr) {
        return root2;
    }
    if (root2 == nullptr) {
        return root1;
    }
    if (root1->y > root2->y) {
        root1->r = merge(root1->r, root2);
        relax(root1);
        return root1;
    } else {
        root2->l = merge(root1, root2->l);
        relax(root2);
        return root2;
    }
}

pair<Node *, Node *> split_key(Node *root, long long val) {
    if (root == nullptr) {
        return make_pair(nullptr, nullptr);
    }
    if (root->x >= val) {
        auto [res1, res2] = split_key(root->l, val);
        root->l = res2;
        relax(root);
        return make_pair(res1, root);
    } else {
        auto [res1, res2] = split_key(root->r, val);
        root->r = res1;
        relax(root);
        return make_pair(root, res2);
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<long long> pr_sum(n + 1);
    for (int i = 0; i < n; ++i) {
        pr_sum[i + 1] = pr_sum[i] + a[i];
    }
    vector<long long> ans(n + 1);
    Node *root = new Node(inf + 10, pr_sum[0]);
    for (int i = 0; i < n; ++i) {
        long long l = 0, r = inf;
        while (l < r - 1) {
            long long m = (l + r) / 2;
            auto [res1, res2] = split_key(root, m);
            if (abs(pr_sum[i + 1] - mn(res2)) >= m || abs(pr_sum[i + 1] - mx(res2)) >= m) {
                l = m;
            } else {
                r = m;
            }
            root = merge(res1, res2);
        }
        ans[i + 1] = l;
        auto [res1, res2] = split_key(root, ans[i + 1]);
        Node *add = new Node(ans[i + 1], pr_sum[i + 1]);
        root = merge(res1, merge(add, res2));
    }
    while (q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int l, r;
            cin >> l >> r;
            l--;
            cout << ans[r] << '\n';
        } else {
            assert(false);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}