Trên một con đường thẳng có N tòa nhà, tòa nhà thứ i có chiều cao H_i. Một người đứng ở đầu con đường (vị trí 0, trước tòa nhà 1) nhìn về phía cuối đường. Một tòa nhà sẽ được người đó nhìn thấy nếu như không có bất kỳ tòa nhà nào đứng trước nó có chiều cao lớn hơn hoặc bằng nó. Hãy đếm số lượng tòa nhà mà người đó có thể nhìn thấy.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Hi (1 <= Hi <= 10^9).

Output: Số lượng tòa nhà có thể nhìn thấy.

Ví dụ:

Input:

6
3 1 4 2 4 5

Output:

3

(Giải thích: Các tòa nhà nhìn thấy là 3 (vị trí 1), 4 (vị trí 3) và 5 (vị trí 6)).

Thư viện trung tâm Học Công Nghệ có N tập tài liệu, tập thứ i có P_i trang. Các tập tài liệu này phải được đọc theo đúng thứ tự từ 1 đến N. Có M học viên được giao nhiệm vụ đọc hết chỗ tài liệu này, mỗi học viên phải đọc một dải các tập tài liệu liên tiếp nhau. Để công bằng, thầy giáo muốn phân chia sao cho "số trang nhiều nhất mà một học viên phải đọc" là nhỏ nhất có thể. Hãy tính con số tối ưu này.

Input:

Dòng 1: N, M (1 <= M <= N <= 10^5).

Dòng 2: N số nguyên Pi (1 <= Pi <= 10^4).

Output: Số trang cực đại nhỏ nhất mà một người phải đọc.

Ví dụ:

Input:

4 2
10 20 30 40

Output:

60

(Giải thích: Học viên 1 đọc tập 1, 2, 3 (tổng 60 trang). Học viên 2 đọc tập 4 (40 trang). Số trang nhiều nhất là 60).

Hệ thống mật mã RSA yêu cầu phân tích một số nguyên dương N thành các thừa số nguyên tố: N = p1^k1 * p2^k2 * ... * pm^km (với pi là số nguyên tố). Mã khóa bảo mật của hệ thống được tính bằng tổng của tất cả các cơ số nguyên tố p_i cộng lại (p1 + p2 + ... + pm). Hãy viết chương trình tính mã khóa này cho số N.

Input: Một số nguyên dương N (2 <= N <= 10^12).

Output: Mã khóa bảo mật (tổng các thừa số nguyên tố phân biệt).

Ví dụ:

Input:

120

Output:

10

(Giải thích: 120 = 2^3 * 3^1 * 5^1. Mã khóa = 2 + 3 + 5 = 10).

Có N học sinh đang hái chè tại đồi chè Tân Cương. Bất chợt trời đổ mưa to. Dọc đồi chè có đúng N lán trú mưa. Học sinh thứ i đang đứng ở tọa độ Xi, lán trú thứ j nằm ở tọa độ Yj. Mỗi lán chỉ chứa được đúng 1 người. Mỗi bước di chuyển (trái hoặc phải) tốn 1 giây. Các em có thể chạy đồng thời cùng lúc. Hãy tìm cách xếp mỗi em vào một lán sao cho thời gian người chạy lâu nhất là nhỏ nhất có thể (để tất cả đều an toàn sớm nhất).

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Xi là vị trí học sinh (-10^9 <= Xi <= 10^9).

Dòng 3: N số nguyên Yj là vị trí lán trú (-10^9 <= Yj <= 10^9).

Kết quả ra: Thời gian chạy tối thiểu của người chậm nhất.

Ví dụ:

Input:

3
-10 -79 -79
-2 9 20

Output:

99

Một số được gọi là T-prime nếu nó có đúng 3 ước số. Hãy đếm số lượng số T-prime không vượt quá N.

Dữ liệu vào:

Dòng 1: N (1 <= N <= 10^12).

Dữ liệu ra:

Số lượng số T-prime.

Ví dụ:

Input:

10

Output:

2

Giải thích: 4 (1,2,4), 9 (1,3,9)