Bạn An rất thích gấp hạc giấy. Mỗi ngày, tranh thủ những lúc rảnh rỗi, An lại lấy giấy ra đề gấp hạc. Những con hạc sau khi gấp sẽ được xâu chuỗi lại. Vì phải bận học bài nên mỗi ngày bạn An gấp được không quá ~k~ hạc giấy.

Yêu cầu

Hãy cho biết bạn An phải gấp hạc trong ít nhất bao nhiêu ngày đề xâu được thành một chuỗi gồm ~n~ hạc giấy?

Dữ liệu đầu vào

Gồm một dòng duy nhất ghi hai số nguyên ~n~ và ~k~ tương ứng là số hạc cần gấp và số hạc có thể gấp nhiều nhất trong một ngày ~(1 \le n, k \le 10^{15})~.

Dữ liệu đầu ra

Gồm một dòng ghi một số nguyên là số ngày ít nhất để bạn An gấp đủ ~n~ hạc giấy.

Ví dụ

Ví dụ 1

INPUT

10 3

OUTPUT

4

Trong một cuộc thi lập trình tại trường, ban tổ chức đưa ra một thử thách: "Tìm số nguyên tố lớn nhất trong một danh sách các số nguyên cho trước". Mặc dù các thí sinh đều đã biết số nguyên tố là số nguyên dương có đúng hai ước số là ~1~ và chính nó, tuy nhiên việc tìm ra được số nguyên tố lớn nhất là không dễ dàng vì danh sách các số nguyên mà ban tổ chức đưa ra là rất lớn.

Yêu cầu

Cho số nguyên dương ~n~ và dãy ~n~ số nguyên ~a_1, a_2, ..., a_n~. Hãy lập trình tìm số nguyên tố lớn nhất trong dãy số đã cho.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~n~ ~(0 < n \le 10^6)~.
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^6;\ i = 1..n)~.

Dữ liệu đầu ra

Gồm một dòng ghi một số nguyên là số nguyên tố lớn nhất tìm được trong dãy số đã cho. Nếu trong dãy không có số nào là số nguyên tố thì in ra số ~-1~.

Ràng buộc dữ liệu

• Có 60% số điểm tương ứng 60% số test có ~0 < n \le 10^3~ và ~|a_i| \le 10^3~.
• Có 20% số điểm tương ứng 20% số test có ~0 < n \le 10^3~ và ~|a_i| \le 10^6~.
• Có 20% số điểm tương ứng 20% số test có ~10^3 < n \le 10^6~ và ~|a_i| \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

6
10 -7 3 15 11 8

OUTPUT

11

Trong truyện cổ tích Ăn khế trả vàng, người em đã làm theo đúng lời chim thần may túi ba gang ra đào hoang lấy vàng. Trên hòn đảo có tất cả ~n~ khối vàng nằm thành hàng dọc dọc theo lối đi, khối thứ ~i~ có khối lượng ~a_i~. Vẫn là người chất phác lại không tham lam nên người em chỉ muốn lấy một số vàng liên tiếp rồi nhanh chóng về nhà, tất nhiên là tổng khối lượng không được vượt quá ~M~ là khả năng chở của chim thần.

Yêu cầu

Hãy cho biết người em có bao nhiêu cách chọn ra các khối vàng liên tiếp sao cho tổng khối lượng của các khối được chọn không vượt quá ~M~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi hai số nguyên dương ~n~ và ~M~ ~(0 < n \le 10^5;\ 0 < M \le 10^9)~.
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 < a_i \le 10^9;\ i = 1..n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách chọn các khối vàng liên tiếp sao cho tổng khối lượng của các khối được chọn không vượt quá ~M~.

Ràng buộc dữ liệu

• Có 70% số điểm tương ứng 70% số test có ~0 < n \le 10^2~.
• Có 20% số điểm tương ứng 20% số test có ~10^2 < n \le 10^3~.
• Có 10% số điểm tương ứng 10% số test có ~10^3 < n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

6 10
8 2 4 15 10 9

OUTPUT

7

Tham gia buổi diễu hành kỉ niệm ngày lễ Quốc khánh có ~n~ học sinh được xếp thành một hàng dài. Các học sinh được đánh số từ ~1~ đến ~n~ từ đầu hàng đến cuối hàng, học sinh thứ ~i~ có chiều cao ~a_i~. Thầy giáo phụ trách nhận thấy có một số học sinh đứng phía trước có chiều cao cao hơn những học sinh đứng sau, điều này làm giảm tính thẩm mỹ khi đoàn diễu hành qua lễ đài. Độ thẩm mỹ của đoàn điều hành phụ thuộc vào số cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau, số cặp này càng nhiều thì độ thẩm mỹ càng giảm.

Yêu cầu

Hãy cho biết có bao nhiêu cập học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6;\ i = 1..n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau.

Ràng buộc dữ liệu

• Có 70% số điểm tương ứng 70% số test có ~1 \le n \le 10^3~.
• Có 20% số điểm tương ứng 20% số test có ~10^3 < n \le 10^5~.
• Có 10% số điểm tương ứng 10% số test có ~10^5 < n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

5
7 8 5 9 4

OUTPUT

6

Giải thích: Có ~6~ cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau là ~(7, 5); (7, 4); (8, 5); (8, 4); (5, 4); (9, 4)~.