pair<int, pair<int, int>> solve(vi& a, int l, int r) {
    if (l == r) {
        return { (long long)a[l] * a[l], {l, r} };
    }
    int m = (l + r) >> 1;
    auto a1 = max(solve(a, l, m), solve(a, m + 1, r));
    int L = m, R = m + 1;
    int sl = a[L], sr = a[R];
    int ml = a[L], mr = a[R];
    pair<int, pair<int, int>> ans = { min(ml, mr) * (sl + sr), {L, R} };
    while (L > l || R < r) {
        bool ok = 1;
        while (L > l) {
            --L;
            if (min(ml, a[L]) >= mr) {
                ml = min(ml, a[L]);
                sl += a[L];
                ans = max(ans, { (long long)mr * (sl + sr) , {L, R} });
                ok = 0;
            }
            else {
                ++L;
                break;
            }
        }
        if (R < r) {
            ++R;
            ok = 0;
            mr = min(mr, a[R]);
            sr += a[R];
            ans = max(ans, { mr * (sl + sr) , {L, R} });
        }
        if (ok) break;
    }
    L = m, R = m + 1;
    sl = a[L], sr = a[R];
    ml = a[L], mr = a[R];
    while (L > l || R < r) {
        bool ok = 1;
        while (R < r) {
            ++R;
            if (min(mr, a[R]) >= ml) {
                mr = min(mr, a[R]);
                sr += a[R];
                ans = max(ans, { ml * (sl + sr) , {L, R} });
                ok = 0;
            }
            else {
                --R;
                break;
            }
        }
        if (L > l) {
            --L;
            ok = 0;
            ml = min(ml, a[L]);
            sl += a[L];
            ans = max(ans, { ml * (sl + sr) , {L, R} });
        }
        if (ok) break;
    }

    return max(ans, a1);
}