Cho số nguyên dương ~N~. Hãy tính

~S = \dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \dots + \dfrac{1}{(N-1)\cdot N}~.

Yêu cầu

Tính giá trị ~S~ và in ra kết quả làm tròn đến ~5~ chữ số thập phân.

Dữ liệu

• Gồm một số nguyên dương ~N~.

Kết quả

• In ra một số là giá trị của ~S~, làm tròn đến ~5~ chữ số thập phân.

Ví dụ

Ví dụ 1

Input

3

Output

0.66667

Ví dụ 2

Input

2

Output

0.50000

Giải thích

Ví dụ 1

~S = \dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} = \dfrac{1}{2} + \dfrac{1}{6} = \dfrac{2}{3}~.

Ví dụ 2

~S = \dfrac{1}{1\cdot 2} = \dfrac{1}{2}~.

Ràng buộc và chấm điểm

Ràng buộc

~2 \le N \le 10^{18}~.

Chấm điểm

• Subtask 1 (~80\%~): ~N \le 10^6~.
• Subtask 2 (~20\%~): Không có ràng buộc gì thêm.

Cho dãy số nguyên ~a_1, a_2, \dots, a_n~. Với mỗi phần tử ~a_i~, được phép chọn đúng một trong ba giá trị:

~a_i - 1~, ~a_i~, ~a_i + 1~.

Hỏi có thể tạo ra một dãy không giảm hay không.

Yêu cầu

Với mỗi bộ test, in ra YES nếu có thể tạo được một dãy không giảm. Ngược lại in ra NO.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~T~ là số bộ test.

• Với mỗi bộ test:

  • Dòng đầu chứa số nguyên dương ~n~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Kết quả

In ra ~T~ dòng. Mỗi dòng là đáp án của một bộ test.

Ví dụ

Ví dụ 1

Input

2
5
1 2 1 1 2
4
1 4 2 1

Output

YES
NO

Giải thích

Ví dụ 1

Với bộ test thứ nhất, có thể chọn dãy ~0, 1, 1, 1, 1~, nên đáp án là YES.

Với bộ test thứ hai, không có cách chọn nào để dãy thu được là không giảm.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le T \le 3~.

~2 \le n \le 10^5~.

~|a_i| \le 10^9~.

Chấm điểm

• Subtask 1 (~50\%~): ~T = 1~, ~a_2 = a_3 = \dots = a_n~.
• Subtask 2 (~30\%~): ~T = 2~, ~n \le 20~.
• Subtask 3 (~20\%~): ~T = 3~.

Cho dãy số nguyên ~A_1, A_2, \dots, A_N~ và hai số nguyên ~U, V~ với ~1 \le U \le V \le N~.

Hãy tìm một dãy con liên tiếp có độ dài ~D~ thỏa ~U \le D \le V~ sao cho tổng các phần tử trên dãy con là lớn nhất.

Yêu cầu

In ra tổng lớn nhất của một dãy con liên tiếp có độ dài nằm trong đoạn ~[U, V]~.

Dữ liệu

• Dòng đầu chứa ba số nguyên dương ~N, U, V~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~.

Kết quả

In ra ~stdout~ một số nguyên là tổng lớn nhất cần tìm.

Ví dụ

Ví dụ 1

Input

6 2 2
-2 3 1 2 5 4

Output

9

Ví dụ 2

Input

5 2 3
-4 3 -2 -6 5

Output

1

Giải thích

Ví dụ 1

Do ~U = V = 2~, ta cần tìm đoạn dài đúng ~2~. Đoạn ~[5, 4]~ có tổng bằng ~9~.

Ví dụ 2

Đoạn ~[3, -2]~ có độ dài ~2~ và tổng bằng ~1~, là lớn nhất.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le U \le V \le N \le 10^5~.

~|A_i| \le 10^9~.

Chấm điểm

• Subtask 1 (~50\%~): ~U = V~.
• Subtask 2 (~50\%~): Không có ràng buộc gì thêm.

Có ~N~ thiết bị, thiết bị thứ ~i~ có giá thuê ~A_i~.

Cần chia toàn bộ ~N~ thiết bị thành một số nhóm. Với mỗi nhóm, tiền thuê được tính theo một trong hai chính sách sau:

• Nếu nhóm có ít nhất ~3~ thiết bị, khách hàng được miễn phí đúng ~1~ thiết bị có giá nhỏ nhất trong nhóm đó.
• Nếu nhóm có ít hơn ~3~ thiết bị, tất cả thiết bị trong nhóm đều được giảm ~q%~.

Yêu cầu

Tính tổng số tiền nhỏ nhất cần trả để thuê hết ~N~ thiết bị.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương ~N, q~.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~.

Kết quả

In ra ~stdout~ một số là tổng chi phí nhỏ nhất.

Ví dụ

Ví dụ 1

Input

6 10
1000 100 900 100 800 100

Output

2100

Giải thích

Ví dụ 1

Chia thành hai nhóm:

• Nhóm ~{100, 100, 100}~ trả ~200~.
• Nhóm ~{800, 900, 1000}~ trả ~1700~.

Tổng chi phí là ~200 + 1700 = 2100~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le N \le 10^6~.

~0 \le q < 100~.

~1 \le A_i \le 10^6~.

~A_i~ chia hết cho ~100~.

Chấm điểm

• Subtask 1 (~20\%~): ~N \le 3~, ~100 \le A_i \le 1000~.
• Subtask 2 (~80\%~): Không có ràng buộc gì thêm.