Cô giáo muốn chọn ra K bạn học sinh trong lớp gồm N bạn để lập thành một nhóm múa. Mỗi bạn có chiều cao A[i]. Để đội hình đẹp, cô muốn chênh lệch giữa bạn cao nhất và bạn thấp nhất trong nhóm K bạn này là nhỏ nhất. Hãy tìm độ chênh lệch nhỏ nhất đó.

Dữ liệu vào:

Dòng đầu chứa hai số N và K.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Độ chênh lệch nhỏ nhất (Min(Max - Min) của tập con K phần tử).

Giới hạn:

2 <= K <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 3 
10 100 30 20 25

Output:

10

(Giải thích: Chọn 20, 25, 30. Chênh lệch 30 - 20 = 10)

Ví dụ 2:

Input:

6 3 
1 15 4 10 8 20

Output:

6

(Giải thích: Chọn 4, 8, 10. Chênh lệch 10 - 4 = 6)

Trong một cuộc bầu cử lớp trưởng, các ứng viên được đánh số. Mảng A gồm N phần tử ghi lại phiếu bầu, trong đó A[i] là mã số của ứng viên được chọn trong phiếu thứ i. Hãy tìm mã số của ứng viên nhận được nhiều phiếu bầu nhất. Nếu có nhiều người cùng số phiếu cao nhất, in ra người có mã số nhỏ nhất.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Mã số của ứng viên chiến thắng.

Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

6 
1 2 2 1 3 1

Output:

1

Ví dụ 2:

Input:

4 
5 2 5 2

Output:

2

(Giải thích: 2 và 5 đều xuất hiện 2 lần, nhưng 2 nhỏ hơn 5 nên in 2)

Cho dãy số nguyên dương A gồm N phần tử. Hãy sắp xếp lại dãy số này sao cho tổng: S = A[0]x1 + A[1]x2 + ... + A[N-1]xN đạt giá trị lớn nhất (với chỉ số mảng tính từ 0). In ra giá trị S đó (Lấy dư cho 10^9 + 7 nếu cần, nhưng ở bài này giới hạn nhỏ nên cứ in số long long).

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Giá trị tổng lớn nhất S. Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^6 (Lưu ý: Kết quả có thể lên tới 10^18, dùng long long)

Ví dụ 1:

Input:

3 
2 1 3

Output:

14

(Giải thích: Sắp xếp thành 1, 2, 3. Tổng = 1x1 + 2x2 + 3x3 = 1+4+9 = 14)

Ví dụ 2:

Input:

2
10 10

Output: 30

(Giải thích: 10x1 + 10x2 = 30)

Một danh sách đầy đủ phải chứa các số từ 1 đến N. Tuy nhiên người ta nhập thiếu mất 1 số, nên dãy chỉ còn N-1 số. Hãy tìm số bị thiếu đó.

Dữ liệu vào:

Dòng đầu chứa số nguyên N (dãy hiện tại có N-1 số).

Dòng thứ hai chứa N-1 số nguyên, các số đều khác nhau và nằm trong khoảng [1, N].

Dữ liệu ra:

Số bị thiếu.

Giới hạn:

2 <= N <= 10^5

Ví dụ 1:

Input:

5 
1 2 4 5

Output:

3

Ví dụ 2:

Input:

4 
4 1 3

Output:

2

Cho dãy số A gồm N phần tử. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) sao cho i < j và A[i] = A[j].

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Số lượng cặp phần tử bằng nhau.

Giới hạn:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ 1:

Input:

5 
2 1 2 2 3

Output:

3

(Giải thích: Các cặp giá trị 2 là (vị trí 0, 2), (0, 3), (2, 3))

Ví dụ 2:

Input:

3 
1 2 3

Output:

0

Tí có N thanh gỗ với độ dài khác nhau. Tí muốn ghép các thanh gỗ này thành các hình chữ nhật. Mỗi hình chữ nhật cần 2 cặp cạnh bằng nhau (ví dụ 2 thanh dài L và 2 thanh dài W). Tí muốn chọn ra 4 thanh gỗ để ghép thành 1 hình chữ nhật sao cho diện tích của nó là lớn nhất có thể. Nếu không thể ghép được, in ra 0.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Diện tích hình chữ nhật lớn nhất.

Giới hạn:

4 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

8 
2 5 2 5 5 2 2 10

Output:

10

Giải thích: Có 4 thanh 2 và 3 thanh 5. Ta có thể ghép hình chữ nhật 2x5. Diện tích 10. Thanh 10 ko có cặp nên bỏ.

Ví dụ 2:

Input:

5 
1 2 3 4 5

Output:

0

Cho 2 dãy số A và B đều có N phần tử. Bạn được phép hoán đổi vị trí các phần tử trong mỗi dãy tùy ý. Nhiệm vụ của bạn là làm sao để tổng S = A[0]xB[0] + A[1]xB[1] + ... + A[N-1]xB[N-1] là nhỏ nhất có thể.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa dãy A.

Dòng thứ ba chứa dãy B.

Dữ liệu ra:

Giá trị nhỏ nhất của S.

Giới hạn:

1 <= N <= 10^5

|A[i]|, |B[i]| <= 10^6 (Kết quả dùng long long)

Ví dụ 1:

Input:

3 
1 2 3 
4 5 6

Output:

28

Giải thích: Sắp A tăng dần 1 2 3, B giảm dần 6 5 4. Tổng: 16 + 25 + 34 = 6+10+12 = 28. Nếu để nguyên là 14+25+36 = 32

Ví dụ 2:

Input:

2 
10 20 
-5 5

Output:

-50

Giải thích: 10x5 + 20x(-5) = 50 - 100 = -50