Cho một số nguyên dương ~n~ ~(n \le 10^{18})~.

Yêu cầu

Hãy tìm số nguyên dương ~k~ lớn nhất thỏa mãn điều kiện: ~1 + 2 + 3 + ... + k \le n~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa một số nguyên dương ~n~.

Dữ liệu đầu ra

Gồm một số nguyên dương ~k~ thỏa mãn yêu cầu bài toán.

Ràng buộc dữ liệu

• Có 80% số test ứng với 80% số điểm của bài thỏa mãn: ~n \le 10^6~;
• 20% số test còn lại ứng với 20% số điểm của bài thỏa mãn: ~10^6 < n \le 10^{18}~.

Ví dụ

Ví dụ 1

INPUT

5

OUTPUT

2

Giải thích: Với ~n = 5~ thì giá trị ~k = 2~ là lớn nhất thỏa mãn ~1 + 2 \le 5~.

Ví dụ 2

INPUT

6

OUTPUT

3

Giải thích: Với ~n = 6~ thì giá trị ~k = 3~ là lớn nhất thỏa mãn ~1 + 2 + 3 \le 6~.

BigZero có một bể cá với đàn cá nhiều màu sắc. Hằng ngày sau những giờ học bài, cậu thường ngồi ngắm đàn cá và cho chúng ăn. Thức ăn của cá được đựng trong các gói đóng sẵn. Mỗi ngày đàn cá ăn hết đúng ~3~ gói, giá bán thức ăn thường xuyên biến động. Cửa hàng cho biết trước giá bán trong ~n~ ngày lần lượt là ~a_1, a_2, ..., a_n~, mỗi ngày được mua nhiều gói với giá bán của ngày đó, thức ăn thừa có thể được dùng cho các ngày tiếp theo. BigZero đang lên kế hoạch để mua thức ăn cho đàn cá trong ~n~ ngày sao cho tiết kiệm nhất.

Yêu cầu

Cho số nguyên dương ~n~ và các số nguyên dương ~a_1, a_2, ..., a_n~, trong đó ~a_i~ là giá bán một gói thức ăn trong ngày thứ ~i~ ~(1 \le i \le n \le 10^6;\ a_{i} \le 10^9)~. Hãy xác định số tiền tối thiểu để mua thức ăn cho đàn cá trong ~n~ ngày.

Dữ liệu đầu vào

Gồm hai dòng:

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

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số tiền tối thiểu để mua thức ăn cho đàn cá trong ~n~ ngày.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~a_1 \le a_2 \le ... \le a_n~;
• Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: ~a_1 \ge a_2 \ge ... \ge a_n~;
• 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

3
2 3 5

OUTPUT

18

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~9~ gói với giá là ~2~;
• Ngày ~2, 3~ không mua gói nào.

Số tiền tối thiểu để mua thức ăn là: ~9 \times 2 + 0 \times 3 + 0 \times 5 = 18~.

Ví dụ 2

INPUT

3
5 3 2

OUTPUT

30

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~3~ gói với giá là ~5~;
• Ngày ~2~ mua ~3~ gói với giá là ~3~;
• Ngày ~3~ mua ~3~ gói với giá là ~2~.

Số tiền tối thiểu để mua thức ăn là: ~3 \times 5 + 3 \times 3 + 3 \times 2 = 30~.

Ví dụ 3

INPUT

3
5 2 3

OUTPUT

27

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~3~ gói với giá là ~5~;
• Ngày ~2~ mua ~6~ gói với giá là ~2~;
• Ngày ~3~ không mua gói nào.

Số tiền tối thiểu để mua thức ăn là: ~3 \times 5 + 6 \times 2 + 0 \times 3 = 27~.

Số nguyên tố là số tự nhiên lớn hơn ~1~ và chỉ có đúng hai ước là ~1~ và chính nó. Ví dụ các số tự nhiên ~2, 3, 5, 7, 11, 13, 17, 19, 23, ...~ là các số nguyên tố.

Yêu cầu

Cho số tự nhiên ~n~, hãy tìm số tự nhiên ~p~ thỏa mãn điều kiện: ~p~ là số nguyên tố nhỏ nhất và ~p \ge n~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~Q~ ~(Q \le 10^6)~ là số bộ test.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số tự nhiên ~n~ ~(n \le 10^9)~.

Dữ liệu đầu ra

Gồm ~Q~ dòng, mỗi dòng ghi một số nguyên tố tìm được tương ứng với dữ liệu vào.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~Q = 1, n \le 10^3~;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: ~Q \le 10^2, n \le 10^9~;
• 30% số test còn lại ứng với 30% số điểm của bài thỏa mãn: ~Q \le 10^6, n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

2
5
8

OUTPUT

5
11

Giải thích:

• Với ~n = 5~, số nguyên tố nhỏ nhất ~p \ge n~ là ~5~;
• Với ~n = 8~, số nguyên tố nhỏ nhất ~p \ge n~ là ~11~.

Cho một dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2,..., a_n~ và một số nguyên dương ~m~.

Yêu cầu

Hãy tìm số nguyên dương ~L~ nhỏ nhất sao cho tất cả các dãy con gồm ~L~ phần tử liên tiếp của dãy ~a~ đều có tổng lớn hơn hoặc bằng ~m~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n \le 10^6;\ m \le 10^{18})~.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le i \le n;\ a_i \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên dương ~L~ nhỏ nhất tìm được thỏa mãn yêu cầu bài toán. Nếu không tìm được giá trị thỏa mãn thì ghi ~-1~.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~a_1 \le a_2 \le ... \le a_n~;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: ~n \le 10^3~;
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5 6
3 2 1 4 5

OUTPUT

3

Ví dụ 2

INPUT

4 16
7 1 2 5

OUTPUT

-1