Cho dãy ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Chúng ta biến đổi các số trong dãy theo quy tắc:

• Thay thế ~a_i~ bằng tổng các chữ số của ~a_i~ ~(1 \le i \le n)~;
• Lặp lại thao tác trên cho đến khi giá trị thu được chỉ có ~1~ chữ số.

Ví dụ: ~a_i = 345 \rightarrow 12 \rightarrow 3~.

Yêu cầu

Tìm dãy con liên tiếp không giảm dài nhất thu được từ dãy số sau khi biến đổi.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^{10})~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là độ dài dãy con liên tiếp không giảm dài nhất

Ràng buộc dữ liệu

• Có 10/35 số điểm thỏa mãn ~a_i~ chỉ có ~1~ chữ số.
• Có 7/35 số điểm thỏa mãn ~a_i~ có ~1~ hoặc ~2~ chữ số.
• Có 18/35 số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

6
2 3 5 8 1 2

OUTPUT

4

Giải thích: Dãy ban đầu không cần biến đổi, dãy con liên tiếp không giảm dài nhất là ~2, 3, 5, 8~.

Ví dụ 2

INPUT

5
7 11 14 9 15

OUTPUT

3

Giải thích: Dãy sau khi biến đổi: ~7, 2, 5, 9, 6~. Dãy con liên tiếp không giảm dài nhất là ~2, 5, 9~.

Cho ~n~ quả bóng gồm ~2~ màu xanh và đỏ xếp thành ~1~ hàng ngang đánh số từ ~1~ đến ~n~ theo thứ tự từ trái qua phải.

Chúng ta mã hóa dãy ~n~ quả bóng theo quy tắc:

• Dãy ~n~ quả bóng mã hóa thành ~1~ xâu gồm ký tự ~0~ hoặc ~1~;
• Ký tự thứ ~i~ là ~1~ nếu số lượng quả bóng xanh từ ~i~ đến ~n~ là số lẻ, ngược lại ký tự thứ ~i~ là ~0~ nếu số lượng qua bóng xanh từ ~i~ đến ~n~ là số chẵn.

Yêu cầu

Cho xâu ký tự mã hóa, hãy tìm dãy màu của ~n~ quả bóng ban đầu.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 600000)~;
• Dòng tiếp theo chứa xâu ký tự mã hóa.

Dữ liệu đầu ra

Gồm một xâu ký tự độ dài ~n~, ký tự ~i~ là b hoặc r tương ứng quả bóng ở vị trí ~i~ là màu xanh hoặc đỏ.

Ràng buộc dữ liệu

• Có 20% số điểm thỏa mãn ~n = 2~;
• Có 30% số điểm thỏa mãn ~n \le 20~;
• Có 50% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8
01110100

OUTPUT

brrbbbrr

Số ~d~ ~(1 < d < n)~ được gọi là ước số đặc biệt của ~n~ nếu ~n / d = n \% d~.

Ví dụ: ~n = 8~ thì có ước số đặc biệt là ~3~ vì ~8/3 = 2~ và ~8 \% 3 = 2~.

Yêu cầu

Cho 2 số nguyên dương ~a,\ b~ ~(a < b)~. Với mỗi giá trị ~n~ ~(a \le n \le b)~, hãy tìm ước số đặc biệt của ~n~ và tính tổng số lượng các ước số đặc biệt của ~n~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa hai số nguyên dương ~a,\ b~ ~(1 \le a < b \le 500000)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng số lượng tìm được.

Ràng buộc dữ liệu

• Có 30% số điểm thỏa mãn ~b - a \le 1000~;
• Có 70% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

15 17

OUTPUT

5

Giải thích: Số ~15~ có ~2~ ước số đặc biệt là ~4~ và ~14~. Số ~16~ có hai ước số đặc biệt là ~7~ và ~15~. Số ~17~ có một ước số đặc biệt là ~16~.

Ví dụ 2

INPUT

4 8

OUTPUT

6

Giải thích: Các số ~4, 5, 6, 7~ đều có ~1~ ước số đặc biệt lần lượt là ~3, 4, 5, 6~. Số ~8~ có ~2~ ước số đặc biệt là ~3~ và ~7~. Tổng có ~6~ ước số đặc biệt.

Có ~n~ học sinh tham gia kỳ thi học sinh giỏi tin học, mỗi học sinh đạt số điểm từ ~1~ đến ~10^9~. Quy tắc xếp giải như sau:

• Học sinh đạt điểm cao nhất (có thể có ~1~ hoặc nhiều học sinh) đạt giải nhất hay xếp hạng ~1~;
• Học sinh đạt điểm cao tiếp theo (có thể có ~1~ hoặc nhiều học sinh) đạt giải nhì hay xếp hạng ~2~;
• Tương tự cho các giải (xếp hạng) tiếp theo, ...
• Chỉ xếp giải cho không quá ~1000~ học sinh.

Yêu cầu

Hãy cho biết số điểm của học sinh xếp hạng ~k~ được bao nhiêu điểm?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n,\ k~ ~(1 \le n \le 10^6,\ 1 \le k \le 1000)~;
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~ là số điểm của ~n~ học sinh.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số điểm của học sinh xếp hạng ~k~, khi bảng xếp hạng có ít hơn ~k~ vị trí thì in ra điểm của học sinh xếp cuối cùng.

Ví dụ

Ví dụ 1

INPUT

10 3
4 1 4 1 9 8 9 8 8 8

OUTPUT

4

Ví dụ 2

INPUT

7 4
5 6 5 6 5 6 6

OUTPUT

5