Bedao Regular Contest 19 - Dãy bậc thang

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Bạn hãy tìm dãy số ~b_1, b_2, \ldots, b_k~ dài nhất thỏa mãn:

  • ~1 \le b_1 < b_2 < \ldots < b_k \le n~.

  • ~a_{b_1} + 1 = a_{b_2} + 2 = \ldots = a_{b_k} + k~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng phần tử của dãy ~a~ (~1 \le n \le 10^6~).

Dòng thứ hai chứa ~n~ số nguyên dương mô tả dãy ~a_1, a_2, \ldots a_n~. (~1 \le a_i \le 10^6~, ~1 \le i \le n~).

Output

Dòng thứ nhất in ra một số nguyên dương ~k~ là số lượng phần tử của dãy ~b~ dài nhất tìm được.

Dòng thứ hai in ra ~k~ số nguyên dương mô tả dãy ~b_1, b_2, \ldots, b_k~.

Nếu có nhiều dãy ~b~ thỏa mãn thì in ra một dãy bất kì.

Scoring

Subtask Điểm Giới hạn
1 ~30~ ~n \le 20~
2 ~40~ ~n \le 5000~
3 ~20~ ~n \le 10^5~
4 ~10~ Không có ràng buộc gì thêm

Sample Input 1

7
5 6 1 4 2 3 2

Sample Output 1

4
1 4 6 7

Comments

Please read the guidelines before commenting.