LOJ

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 1e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int n;

int a[N], b[N];

int add[N];

int block;

int pos[N];

int L[N], R[N];

void update(int x)
{
    for (int i = L[pos[x]]; i <= R[pos[x]]; ++i)
        b[i] = a[i];
    sort(b + L[pos[x]], b + R[pos[x]] + 1);
}

signed main()
{
    n = read();
    block = sqrt(n);
    if (n % block)
        block++;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = a[i];
    for (int i = 1; i < block; ++i)
        L[i] = R[i - 1] + 1, R[i] = i * block;
    L[block] = R[block - 1] + 1, R[block] = n;
    for (int i = 1; i <= block; ++i)
    {
        for (int j = L[i]; j <= R[i]; ++j)
        {
            pos[j] = i;
        }
        sort(b + L[i], b + R[i] + 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
        {
            if (pos[l] == pos[r])
            {
                for (int i = l; i <= r; ++i)
                    a[i] += c;
                update(l);
            }
            else
            {
                for (int i = l; i <= R[pos[l]]; ++i)
                    a[i] += c;
                update(l);
                for (int i = pos[l] + 1; i <= pos[r] - 1; ++i)
                    add[i] += c;
                for (int i = L[pos[r]]; i <= r; ++i)
                    a[i] += c;
                update(r);
            }
        }
        else
        {
            int ans = -1;
            if (pos[l] == pos[r])
            {
                for (int i = l; i <= r; ++i)
                    if (a[i] + add[pos[l]] < c)
                        ans = max(ans, a[i] + add[pos[l]]);
            }
            else
            {
                for (int i = l; i <= R[pos[l]]; ++i)
                    if (a[i] + add[pos[l]] < c)
                        ans = max(ans, a[i] + add[pos[l]]);
                for (int i = pos[l] + 1; i <= pos[r] - 1; ++i)
                {
                    int it = lower_bound(b + L[i], b + R[i] + 1, c - add[i]) - b;
                    --it;
                    if (it >= L[i] && b[it] + add[i] < c)
                    {
                        ans = max(ans, b[it] + add[i]);
                    }
                }
                for (int i = L[pos[r]]; i <= r; ++i)
                    if (a[i] + add[pos[r]] < c)
                        ans = max(ans, a[i] + add[pos[r]]);
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}