Subtask ~1~ (~20\%~): ~n \le 20~

Duyệt ~l~, ~r~, ~i_1~, ~i_2~, ~i_3~.

Độ phức tạp: ~\mathcal{O}(n^5)~.

Subtask ~2~ (~20\%~): ~n \le 10^2~

Dễ thấy cách chọn tối ưu luôn có ~l = i_1~ và ~r = i_3~. Thế nên ta chỉ cần duyệt ~i_1~, ~i_2~ và ~i_3~.

Độ phức tạp: ~\mathcal{O}(n^3)~.

Subtask ~3~ (~20\%~): ~n \le 3\times 10^3~

Ta duyệt ~i_1~ và ~i_3~, dễ thấy ~a_{i_2}~ sẽ là số lớn nhất trong khoảng (~i_1~;~i_3~). Ta có thể dễ dàng tìm được ~i_2~ trong lúc duyệt.

Độ phức tạp: ~\mathcal{O}(n^2)~.

Subtask ~4~ (~40\%~): ~n \le 2\times 10^5~

Với nhận xét ở subtask 2, ta có: ~a_{i_1} + a_{i_2} + a_{i_3} - (r - l) = a_{i_2} + (a_{i_1} + i_1) + (a_{i_3} - i_3)~.

Với mỗi ~i~:

• Đặt ~F_i = max(a_{j})~ với ~1 \le j \le i~. Có thể tính bằng công thức ~F_i = max(F_{i+1}, a_i + i)~.
• Đặt ~G_i = max(a_j)~ với ~i \le j \le n~. Có thể tính bằng công thức ~F_i = max(F_{i - 1}, a_i - i)~.
• Kết quả của bài toán là ~max(a_i + F_{i - 1} + G_{i + 1})~ với ~1 \lt i \lt n~.

Độ phức tạp: ~\mathcal{O}(n)~.

int n, a[N], F[N], G[N];

void solve() {
    //input
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    //calculate F and G
    F[1] = a[1] + 1;
    for(int i = 2; i <= n; ++i) {
        F[i] = max(F[i - 1], a[i] + i);
    }
    G[n] = a[n] - n;
    for(int i = n - 1; i >= 1; --i) {
        G[i] = max(G[i + 1], a[i] - i);
    }
    //calculate ans
    int ans = 0;
    for(int i = 2; i < n; ++i) {
        ans = max(ans, a[i] + F[i - 1] + G[i + 1]);
    }
    cout << ans;
}