Trong kỳ thi lập trình của trường Đại học Công nghệ Thông tin và Truyền thông (ICTU), hệ thống yêu cầu sinh viên giải mã một dãy số. Mật mã được giấu kín chính là tích lớn nhất của 3 số bất kỳ trong một mảng gồm N số nguyên (mảng có thể chứa cả số âm, số dương và số 0). Hãy viết chương trình tìm ra mật mã này.

Input:

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

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

Output: Tích lớn nhất của 3 số bất kỳ trong mảng.

Ví dụ:

Input:

5
-10 -10 1 3 2

Output:

300

(Giải thích: Tích của -10 * -10 * 3 = 300).

Một chuỗi DNA được biểu diễn bằng một xâu ký tự chỉ gồm các chữ cái A, C, G, T. Các nhà nghiên cứu muốn tìm ra một đoạn gen (chuỗi con liên tiếp) đồng nhất dài nhất, tức là đoạn gen chỉ chứa một loại ký tự duy nhất. Họ được phép can thiệp để thay đổi tối đa K ký tự trong chuỗi ban đầu thành bất kỳ ký tự nào khác. Hãy tìm chiều dài lớn nhất của đoạn gen đồng nhất có thể đạt được.

Input:

Dòng 1: Hai số nguyên N, K (1 <= N <= 10^5, 0 <= K <= N), N là chiều dài xâu.

Dòng 2: Xâu ký tự S đại diện cho chuỗi DNA.

Output: Chiều dài đoạn gen đồng nhất lớn nhất.

Ví dụ:

Input:

8 2
AACAAGTA

Output:

6

(Giải thích: Thay đổi chữ C và chữ G thành A, ta được đoạn AAAAAA dài 6).

Tại sân vận động, có M vị trí tập kết được đánh tọa độ trên một đường thẳng. Huấn luyện viên cần bố trí N học viên vào các vị trí này. Để đảm bảo không gian khởi động an toàn, khoảng cách giữa 2 học viên đứng gần nhau nhất phải càng lớn càng tốt. Hãy tìm khoảng cách gần nhất lớn nhất có thể đạt được sau khi sắp xếp chỗ cho N học viên.

Input:

Dòng 1: Hai số nguyên M, N (2 <= N <= M <= 10^5).

Dòng 2: M số nguyên Xi là tọa độ các vị trí tập kết (0 <= Xi <= 10^9), không nhất thiết đã sắp xếp.

Output: Khoảng cách ngắn nhất cực đại.

Ví dụ:

Input:

5 3
1 2 8 4 9

Output:

3

(Giải thích: Chọn các vị trí 1, 4, 8. Khoảng cách giữa (1,4) là 3, giữa (4,8) là 4. Khoảng cách ngắn nhất là 3).

Trên con đường chinh phục đỉnh cao tại trung tâm Học Công Nghệ, có N bậc thang. Mỗi bậc thang có một điểm số C_i (có thể âm hoặc dương). Khi bước lên một bậc, bạn sẽ được cộng (hoặc bị trừ) số điểm tương ứng. Bắt đầu từ mặt đất (bậc 0), mỗi bước bạn có thể tiến lên 1 bậc hoặc bước nhảy vọt qua 2 bậc. Tuy nhiên, bạn không được phép nhảy vọt 2 lần liên tiếp. Hãy tìm cách di chuyển để lên đến bậc thứ N sao cho tổng điểm thu được là lớn nhất.

Input:

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

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

Output: Tổng điểm lớn nhất khi đến đích.

Ví dụ:

Input:

4
-1 -2 -3 -4

Output:

-6

Trên mặt phẳng tọa độ cho N điểm phân biệt. Hãy tìm ra 3 điểm trong số N điểm đó sao cho diện tích tam giác tạo thành là lớn nhất. Nếu tất cả các bộ 3 điểm đều thẳng hàng, in ra 0.0.

Đầu vào: Dòng đầu là số nguyên N (3 <= N <= 300). N dòng tiếp theo, mỗi dòng chứa 2 số nguyên x, y (-10^6 <= x, y <= 10^6) là tọa độ của một điểm.

Đầu ra: Diện tích tam giác lớn nhất tìm được, làm tròn 1 chữ số thập phân.

Ví dụ

Input:

4
0 0
0 4
4 0
2 2

Output:

8.0