Bài tập

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Hãy tìm một dãy con tăng nghiêm ngặt dài nhất, tức là dãy các chỉ số \(i_1 < i_2 < \dots < i_k\) với \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) và \(k\) lớn nhất.

Để đáp án là duy nhất, trong số các dãy chỉ số tối ưu hãy chọn dãy nhỏ nhất theo thứ tự từ điển (so sánh \(i_1\) trước, nếu bằng nhau thì so sánh \(i_2\), ...).

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

• Dòng thứ nhất: độ dài \(k\) của dãy con tăng dài nhất.
• Dòng thứ hai: \(k\) chỉ số \(i_1, i_2, \dots, i_k\) (đánh số từ \(1\), theo thứ tự tăng dần) của dãy chỉ số nhỏ nhất theo thứ tự từ điển.

Constraints

• \(1 \le N \le 5000\)
• \(|A_i| \le 10^9\)

Sample Input

7
4 -2 7 7 0 9 3

Sample Output

3
1 3 6

Explanation

Độ dài lớn nhất là \(3\). Các dãy chỉ số tối ưu gồm \((1,3,6)\), \((1,4,6)\), \((2,3,6)\), \((2,4,6)\), \((2,5,6)\), ...; dãy \((1,3,6)\) nhỏ nhất theo thứ tự từ điển.

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Hãy tìm một dãy con tăng nghiêm ngặt dài nhất, tức là dãy các chỉ số \(i_1 < i_2 < \dots < i_k\) với \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) và \(k\) lớn nhất.

Để đáp án là duy nhất, trong số các dãy chỉ số tối ưu hãy chọn dãy nhỏ nhất theo thứ tự từ điển (so sánh \(i_1\) trước, nếu bằng nhau thì so sánh \(i_2\), ...).

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

• Dòng thứ nhất: độ dài \(k\) của dãy con tăng dài nhất.
• Dòng thứ hai: \(k\) chỉ số \(i_1, i_2, \dots, i_k\) (đánh số từ \(1\), theo thứ tự tăng dần) của dãy chỉ số nhỏ nhất theo thứ tự từ điển.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(|A_i| \le 10^9\)

Sample Input

7
8 3 -5 3 6 4 10

Sample Output

4
3 4 5 7

Explanation

Độ dài lớn nhất là \(4\). Có hai dãy chỉ số tối ưu là \((3,4,5,7)\) ứng với \(-5,3,6,10\) và \((3,4,6,7)\) ứng với \(-5,3,4,10\); dãy đầu nhỏ hơn theo thứ tự từ điển.

Ông Geppetto có \(N\) thanh gỗ, thanh thứ \(i\) dài \(A_i\). Để chế tác chiếc mũi cho Pinocchio, ông lặp lại quy trình sau cho tới khi chỉ còn đúng một thanh:

1. Chọn ra hai thanh ngắn nhất hiện có, gọi độ dài của chúng là \(p \le q\) (nếu có nhiều thanh cùng độ dài thì chọn tuỳ ý, kết quả không phụ thuộc cách chọn).
2. Nếu \(p = q\) thì bỏ đi một trong hai thanh.
3. Nếu \(p < q\) thì cắt bớt thanh dài \(q\) đi một đoạn dài \(p\), tức là thanh đó còn lại độ dài \(q - p\).

Khi chỉ còn một thanh, thanh đó là chiếc mũi. Hãy tính độ dài của nó.

Input

• Dòng 1: số nguyên dương \(N\).
• Dòng 2: \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\).

Output

• In ra một số nguyên là độ dài thanh gỗ cuối cùng.

Constraints

• \(1 \le N \le 100000\).
• \(1 \le A_i \le 10^9\).

Sample Input

4
12 18 30 8

Sample Output

2

Explanation

Quy trình giữ nguyên ước chung lớn nhất của cả nhóm nên kết quả là \(\gcd(12, 18, 30, 8) = 2\).

Với mỗi số nguyên \(x \ge 2\), ký hiệu \(f(x)\) là ước lớn nhất của \(x\) nhỏ hơn \(x\) (ví dụ \(f(12) = 6\), \(f(7) = 1\), \(f(9) = 3\)).

Cho số nguyên \(N\). Ta muốn tách \(N\) thành tổng của một hay nhiều số nguyên, mỗi số không nhỏ hơn 2:

Chi phí của một cách tách là \(f(k_1) + f(k_2) + \dots + f(k_m)\). Cách tách chỉ gồm một số (\(m = 1\), \(k_1 = N\)) cũng hợp lệ.

Hãy tính chi phí nhỏ nhất có thể đạt được.

Input

Một dòng duy nhất chứa số nguyên \(N\).

Output

In ra chi phí nhỏ nhất.

Constraints

• \(2 \le N < 10^9\)

Sample Input

27

Sample Output

3

Explanation

Có thể tách \(27 = 7 + 7 + 13\), cả ba số đều là số nguyên tố nên mỗi số có chi phí \(1\), tổng chi phí là \(3\). Không có cách tách nào cho tổng chi phí nhỏ hơn.