Cho một mảng gồm N chữ số (từ 0 đến 9). Bạn hãy ghép một số hoặc tất cả các chữ số này lại với nhau để tạo thành một số nguyên dương lớn nhất có thể và số đó phải chia hết cho 15. Mỗi chữ số trong mảng chỉ được sử dụng tối đa bằng số lần xuất hiện của nó. Nếu không thể tạo ra số nào chia hết cho 15, hãy in ra -1.

Input:

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

Dòng 2: N chữ số di (0 <= di <= 9).

Output: Số nguyên lớn nhất chia hết cho 15.

Ví dụ:

Input:

5
8 1 0 4 3

Output:

8430

Một xâu được gọi là đối xứng nếu đọc từ trái qua phải hay từ phải qua trái đều giống hệt nhau. Cho một xâu ký tự S chỉ gồm các chữ cái in thường, bạn hãy tìm xâu con liên tiếp đối xứng có độ dài lớn nhất nằm trong S. Nếu có nhiều xâu con đối xứng đạt cùng độ dài lớn nhất, hãy in ra xâu xuất hiện đầu tiên.

Input: Một dòng chứa xâu S (Độ dài <= 5000).

Output: Xâu con đối xứng dài nhất.

Ví dụ:

Input:

babad

Output:

bab

Các nhà khoa học đang nghiên cứu một hệ sinh thái gồm N sinh vật xếp thành hàng, sinh vật thứ i có mã loài là A_i. Để khoanh vùng bảo tồn, họ cần chọn một đoạn các sinh vật đứng liên tiếp nhau. Tuy nhiên, để tiện cho việc theo dõi, đoạn được chọn không được chứa quá K loài sinh vật khác nhau. Hãy tìm độ dài của đoạn liên tiếp dài nhất thỏa mãn điều kiện này.

Input:

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

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

Output: Độ dài đoạn liên tiếp lớn nhất.

Ví dụ:

Input:

5 2
1 2 1 3 2

Output:

3

(Giải thích: Đoạn dài nhất là 1 2 1 chứa 2 loài là 1 và 2).

Có N viên ngọc được xâu thành một vòng cổ hình tròn (viên thứ 1 kề với viên thứ 2, ..., viên thứ N kề với viên thứ 1). Viên ngọc thứ i có giá trị là V_i. Bạn được phép lấy ra một số viên ngọc để bán, nhưng do hệ thống báo động, bạn tuyệt đối không được lấy 2 viên ngọc nằm kề nhau trên vòng cổ. Hãy tìm cách chọn ngọc sao cho tổng giá trị thu được là lớn nhất.

Input:

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

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

Output: Tổng giá trị lớn nhất.

Ví dụ:

Input:

4
1 2 3 1

Output:

4

(Giải thích: Chọn viên thứ 2 và thứ 4, tổng = 2 + 1 = 3. Hoặc viên 1 và 3, tổng = 1 + 3 = 4).

Một nông trường chè tại Thái Nguyên có N luống chè, luống thứ i cho sản lượng A_i kg. Để thử nghiệm một loại phân bón mới, kỹ sư nông nghiệp cần chọn một dải gồm ít nhất K luống chè liên tiếp nhau sao cho "sản lượng trung bình" của dải này là lớn nhất có thể. Hãy tìm mức sản lượng trung bình cực đại đó.

Input:

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

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

Output: Sản lượng trung bình lớn nhất (in ra phần nguyên làm tròn xuống của kết quả).

Ví dụ:

Input:

4 2
8 1 9 10

Output:

9

(Giải thích: Chọn đoạn [9, 10] có độ dài 2 >= K, trung bình là 9.5. Làm tròn xuống là 9).