Subtask 1: ~n \le 20~.

Duyệt mọi dãy con của dãy ~a_1, a_2, \ldots, a_n~. Với mỗi dãy con, ta kiểm tra dãy con đó có thỏa mãn điều kiện đề bài hay không?

Subtask 2: ~n \le 5000~.

Đặt ~f_i~ là độ dài dãy con dài nhất thỏa mãn điều kiện đề bài kết thúc tại vị trí ~i~.

Ta có:

$$f_i = \max \begin{cases}1 \\ \max_{j < i, a_j = a_i + 1}f_j + 1 \end{cases}$$

Kết quả bài toán là ~\max_{1 \le i \le n} f_i~.

Subtask 3: Không có ràng buộc gì thêm.

Đặt mảng ~f_i~ như subtask 2.

Nhận xét: Nếu ~1 \le i < j \le n~ và ~a_i = a_j~ thì ~f_i \le f_j~. Do mọi dãy con thỏa mãn điều kiện đề bài kết thúc tại vị trí ~i~ có thể biến đổi bằng cách xóa phần tử ~a_i~ và thay thế bằng phần tử ~a_j~ mà vẫn thỏa mãn điều kiện đề bài.

Vì thế, ta chỉ cần chú ý đến lần cuối cùng 1 giá trị nào đó xuất hiện.

Đặt ~lst_x~ là vị trí cuối cùng giá trị ~x~ xuất hiện.

Ta tính lần lượt các giá trị ~f_i~ với ~i~ tăng dần.

• Nếu giá trị ~a_i + 1~ chưa từng xuất hiện thì ~f_i = 1~.

• Ngược lại, ta có vị trí cuối cùng mà giá trị ~a_i + 1~ xuất hiện là ~lst_{a_i + 1}~ và ~f_i = f_{lst_{a_i + 1}} + 1~.

  Sau đó, cập nhật ~lst_{a_i} = i~.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int a[N];
int n;
int dp[N],mx[N],tv[N];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        dp[i] = dp[mx[a[i]+1]]+1;
        tv[i] = mx[a[i]+1];
        if (dp[mx[a[i]]] < dp[i]) {
            mx[a[i]] = i;
        }
    }
    int res = 0;
    for (int i=1; i<=n; i++) {
        if (dp[i] > dp[res]) res = i;
    }
    cout << dp[res] << '\n';
    vector<int> ans;
    while (res) {
        ans.push_back(res);
        res = tv[res];
    }
    reverse(ans.begin(),ans.end());
    for (auto u : ans) cout << u << ' '; 
}