Trên một tuyến đường cao tốc thẳng tắp có N chiếc xe đang bị hỏng, chiếc xe thứ i nằm ở tọa độ X_i. Lực lượng cứu hộ muốn thiết lập một trạm sửa chữa dã chiến ngay trên tuyến đường này. Để tối ưu hóa thời gian di chuyển, trạm sửa chữa phải được đặt ở một vị trí sao cho tổng khoảng cách từ trạm đến tất cả N chiếc xe là nhỏ nhất. Hãy tính tổng khoảng cách nhỏ nhất đó.

Input:

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

Dòng 2: N số nguyên Xi (0 <= Xi <= 10^9). (Tọa độ không nhất thiết đã sắp xếp).

Output: Tổng khoảng cách nhỏ nhất.

Ví dụ:

Input:

5
1 2 9 4 6

Output:

12

(Giải thích: Đặt trạm tại tọa độ 4 (trung vị). Khoảng cách là |1-4| + |2-4| + |9-4| + |4-4| + |6-4| = 3 + 2 + 5 + 0 + 2 = 12).

Một đoạn gen mục tiêu có cấu trúc là xâu B (gồm M ký tự). Hệ thống cần quét một chuỗi gen mẹ A (gồm N ký tự) để tìm xem có bao nhiêu đoạn gen con liên tiếp trong A mang bộ gen tương đồng với B. Hai đoạn gen được coi là tương đồng nếu chúng chứa số lượng từng loại ký tự hoàn toàn giống nhau (tức là đoạn này là một hoán vị của đoạn kia).

Input:

Dòng 1: Xâu A (Độ dài N <= 10^5).

Dòng 2: Xâu B (Độ dài M <= 10^5). (Các xâu chỉ gồm chữ cái in thường).

Output: Số lượng đoạn gen con của A tương đồng với B.

Ví dụ:

Input:

cbaebabacd
abc

Output:

2

(Giải thích: Các đoạn là "cba" (chỉ số 0-2) và "bac" (chỉ số 6-8)).

Một camera giám sát giao thông quét dọc theo một hàng gồm N chiếc ô tô, chiếc thứ i có tốc độ là V_i. Do góc nhìn giới hạn, tại mỗi thời điểm camera chỉ ghi hình được đúng K chiếc xe liên tiếp. Nhiệm vụ của hệ thống là với mỗi khung hình (đoạn K xe liên tiếp), phải trích xuất ra được tốc độ của chiếc xe chạy nhanh nhất để xử lý vi phạm.

Input:

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

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

Output: In ra N - K + 1 số nguyên, mỗi số là tốc độ lớn nhất trong một khung hình từ trái sang phải.

Ví dụ:

Input:

8 3
1 3 -1 -3 5 3 6 7

Output:

3 3 5 5 6 7

Cho một xâu ký tự S. Bạn được yêu cầu cắt xâu S thành các đoạn con sao cho mỗi đoạn con đều là một xâu đối xứng (Palindrome). Tuy nhiên, mỗi nhát cắt đều tiêu tốn năng lượng. Hãy tìm số lần cắt ít nhất để toàn bộ các đoạn con đều là xâu đối xứng.

Input: Một dòng chứa xâu S chỉ gồm chữ cái in thường (Độ dài <= 2000).

Output: Số nhát cắt ít nhất.

Ví dụ:

Input:

ababbbabbababa

Output:

3

(Giải thích: Cắt thành a | babbbab | b | ababa. Tổng cộng 3 nhát cắt).