Cho mảng ~a~ gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~. Bạn có thể thực hiện hành động biến đổi tại một vị trí chưa từng biến đổi trong mảng và gán giá trị tại vị trí đó thành một số nguyên bất kỳ. Chi phí cho mỗi lần biến đổi tại vị trí ~x~ sang giá trị ~y~ được tính theo công thức ~(a_x - y)^2~.

Yêu cầu:

Hãy tìm chi phí biến đổi nhỏ nhất để tất cả ~n~ số trong mảng trở nên bằng nhau.

Dữ liệu:

Đọc từ tệp EQUAL.INP:

• Dòng 1: Chứa số nguyên dương ~N~ (~1 \le N \le 10^6~)
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le |a_i| \le 10^6~)

Kết quả:

Ghi ra tệp EQUAL.OUT một số nguyên duy nhất — chi phí biến đổi nhỏ nhất.

Ví dụ:

Giới hạn:

• 50% số test: ~n, |a_i| \le 10^3~
• 50% số test: Không có ràng buộc bổ sung

Yêu cầu:

Cho dãy số gồm ~n~ phần tử ~a₁, a₂, …, aₙ~.
Ta cần đếm số dãy con liên tiếp có hiệu giữa phần tử lớn nhất và nhỏ nhất là một số chẵn.

Dữ liệu:

Vào từ tệp EVENSUB.INP:

• Dòng đầu: chứa số nguyên ~n~ (~1 ≤ n ≤ 10⁵~)
• Dòng thứ hai: chứa ~n~ số nguyên ~aᵢ~ (~1 ≤ aᵢ ≤ 10⁹~)

Kết quả:

Ghi ra tệp EVENSUB.OUT một số nguyên duy nhất — là số lượng dãy con liên tiếp có chênh lệch giữa số lớn nhất và nhỏ nhất là số chẵn.

Ví dụ:

Giới hạn:

• 40% test có ~n ≤ 1000~
• 30% test có ~1 ≤ aᵢ ≤ 3~
• 30% test còn lại không có ràng buộc thêm.

Cho ~N~ dãy số không giảm ~A₁, A₂, …, Aₙ~, mỗi dãy gồm ~L~ số nguyên.
Một dãy được gọi là không giảm nếu mỗi phần tử đứng sau lớn hơn hoặc bằng phần tử đứng trước.

Xét hai dãy ~Aᵢ~ và ~Aⱼ~ (~1 ≤ i, j ≤ N~), ta gọi dãy gộp (ký hiệu là ~Aᵢⱼ~) của hai dãy ~Aᵢ~, ~Aⱼ~ là dãy gồm tất cả ~2L~ phần tử của hai dãy, được sắp xếp theo thứ tự không giảm.
Phần tử trung vị của dãy gộp là phần tử đứng ở vị trí thứ ~L~ (đếm từ 1).

Ví dụ:

• Xét hai dãy:
  ~Aᵢ = (1, 3, 4, 5, 6)~, ~Aⱼ = (0, 1, 5, 6, 7)~
  Khi gộp hai dãy ta có:
  ~Aᵢⱼ = (0, 1, 1, 3, 4, 5, 5, 6, 6, 7)~
  → Phần tử trung vị là phần tử thứ 5 = 4.

Yêu cầu:

Tính tổng của tất cả các phần tử trung vị của các dãy gộp ~Aᵢⱼ~ với mọi cặp ~1 ≤ i < j ≤ N~.

Dữ liệu:

Tập tin MEDSUM.INP gồm:

• Dòng đầu chứa hai số nguyên ~N~, ~L~
  (~2 ≤ N ≤ 200~, ~1 ≤ L ≤ 20000~)
• Tiếp theo là ~N~ dòng, mỗi dòng chứa ~L~ số nguyên — là các phần tử của dãy ~Aᵢ~ (~|aᵢⱼ| ≤ 10⁹~).
  Hai số liên tiếp trên cùng dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả:

Ghi ra tệp MEDSUM.OUT một số nguyên duy nhất là giá trị:

~σ mod 10⁹~

Trong đó ~σ~ là tổng của tất cả phần tử trung vị của các dãy gộp ~Aᵢⱼ~ với mọi cặp ~1 ≤ i < j ≤ N~.

Ví dụ:

Giới hạn:

• 50% test thỏa: ~2 ≤ N ≤ 100~, ~1 ≤ L ≤ 300~
• 50% test còn lại không có ràng buộc thêm

Yêu cầu:

Cho dãy ~N~ số nguyên không âm ~a_1, a_2, \ldots, a_N~. Hãy tìm một dãy con liên tiếp gồm các số nguyên tố tăng dần dài nhất của dãy.
Nếu có nhiều dãy con thỏa mãn, chọn dãy có chỉ số nhỏ nhất.

Dữ liệu:

Đọc từ tệp PRIMEHIGHER.INP gồm 2 dòng:

• Dòng 1: Ghi số nguyên ~N~ (~0 < N < 1000~)
• Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ (~a_i < 10^9~)

Kết quả:

Ghi ra tệp PRIMEHIGHER.OUT gồm 2 dòng:

• Dòng 1: Ghi độ dài của dãy số nguyên tố liên tiếp tăng dần dài nhất tìm được.
• Dòng 2: Ghi dãy số nguyên tố tìm được, các số cách nhau đúng 1 khoảng trắng.

Ví dụ:

Input:

8  
2 5 3 4 5 7 11 6

Output:

3  
5 7 11

Giới hạn:

• ~0 < N < 1000~
• ~a_i < 10^9~
• 50% số test ứng với ~N < 100~
• 50% số test ứng với ~100 < N < 1000~

Cho dãy gồm ~n~ số nguyên ~a₁, a₂, …, aₙ~. Một đoạn con của dãy là dãy liên tiếp ~aᵢ, aᵢ₊₁, …, aⱼ~ (~1 ≤ i ≤ j ≤ n~).
Độ dài của đoạn con là ~(j - i + 1)~, và trọng số của đoạn con là tổng các phần tử trong đoạn đó:
~aᵢ + aᵢ₊₁ + … + aⱼ~.

Yêu cầu:

Hãy tìm hai đoạn con không có phần tử chung, mỗi đoạn có độ dài chia hết cho 3, sao cho tổng trọng số của hai đoạn con là lớn nhất.

Dữ liệu:

Tập tin Seq.inp gồm:

• Dòng đầu: ghi số nguyên ~n~ (~n ≥ 10^6~)
• Dòng thứ hai: ghi ~n~ số nguyên ~a₁, a₂, …, aₙ~ (~|aᵢ| ≤ 10⁹~)

Kết quả:

Tập tin Seq.out ghi một số nguyên duy nhất là tổng trọng số lớn nhất của hai đoạn con thỏa mãn điều kiện.

Ví dụ:

Giới hạn:

• 30% test có ~n ≤ 20~
• 30% test có ~n ≤ 200~
• 20% test có ~n ≤ 2000~
• 20% test còn lại có ~n ≤ 200000~

Yêu cầu:

Cho một xâu ký tự ~S~ độ dài ~N~, hãy tìm xâu con đối xứng dài nhất bắt đầu từ ký tự đầu tiên của ~S~.
Kết quả cần trả về là độ dài của xâu con đối xứng này.

Dữ liệu:

Đọc từ tệp Paliny.inp gồm:

• Dòng 1: Số nguyên ~N~ — số lượng ký tự của xâu ~S~ (~1 \le N \le 50000~)
• Dòng 2: Xâu ký tự ~S~ độ dài ~N~

Kết quả:

Ghi ra tệp Paliny.out một số nguyên duy nhất — độ dài của xâu con đối xứng dài nhất bắt đầu từ ký tự đầu tiên.

Ví dụ:

Input:

5  
abacd

Output:

3

Giới hạn:

• ~1 \le N \le 50000~
• 30% số test có ~1 \le N \le 100~
• 30% số test có ~100 \le N \le 1000~
• 40% số test có ~1000 \le N \le 50000~