Trong một cuộc thi lập trình, Ban Tổ chức đưa ra ~N~ thẻ số, mỗi thẻ ghi một dãy chữ số (dãy gồm các chữ số liên tiếp được tạo thành từ các chữ số ~0, 1, 2, \ldots, 9~). Các thẻ số này được cắt ra từ một số tự nhiên rất lớn được viết liên tiếp và đảm bảo tồn tại ít nhất một thẻ có chữ số đầu tiên khác ~0~. Các thẻ được xáo trộn nhưng thứ tự các chữ số trên mỗi thẻ vẫn được giữ nguyên. Bằng kỹ năng của mình, các thí sinh dự thi phải tìm cách sắp xếp lại thứ tự các thẻ sao cho tạo được số theo yêu cầu trong thời gian cho phép.

Yêu cầu

Hãy sắp xếp thứ tự các thẻ số sao cho số tự nhiên thu được có giá trị lớn nhất.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^5)~ là số lượng thẻ số;
• ~N~ dòng tiếp theo, mỗi dòng chứa một dãy liên tiếp các chữ số có độ dài tối đa ~30~, lần lượt là các thẻ số.

Dữ liệu đầu ra

Ghi ra một số tự nhiên duy nhất theo yêu cầu.

Ràng buộc dữ liệu

• Subtask 1: Có ít nhất 50% số test có ~N \le 10^2~, các thẻ đều có số chữ số là ~1~;
• Subtask 2: Có ít nhất 35% số test có ~N \le 10^3~, các thẻ đều có cùng số chữ số và số chữ số tối đa là ~30~;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

3
6
1
3

OUTPUT

631

Giải thích: Các số có thể tạo ra từ ~3~ thẻ là: ~613, 631, 163, 136, 316, 361~. Số lớn nhất là ~631~.

Ví dụ 2

INPUT

4
67
20
2
111

OUTPUT

67220111

Giải thích: Trong các số tạo ra từ ~4~ thẻ, số lớn nhất là ~67220111~.

Cho một bảng kích thước ~N \times N~, mỗi ô của bảng chứa một số nguyên. Thực hiện một đường cắt ngang và một đường cắt dọc chia bảng thành bốn phần là các hình chữ nhật hoặc hình vuông. Với mỗi cách cắt, giá trị của mỗi phần là tổng các số nguyên trong phần đó.

Yêu cầu

Hãy xác định chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(2 \le N \le 10^3)~;
• ~N~ dòng tiếp theo, mỗi dòng gồm ~N~ số nguyên có giá trị tuyệt đối không quá ~10^9~. Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

Dữ liệu đầu ra

Ghi ra một số nguyên duy nhất là kết quả cần tìm.

Ràng buộc dữ liệu

• Subtask 1: Có ít nhất 35% số test có ~N \le 3~;
• Subtask 2: Có ít nhất 14% số test có ~N = 4~;
• Subtask 3: Có ít nhất 20% số test có ~4 < N \le 10^2~;
• Subtask 4: Số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

2
1 2
3 4

OUTPUT

3

Giải thích: Có ~1~ cách cắt.

Chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất: ~3~.

Ví dụ 2

INPUT

3
1 2 2
1 -1 4
2 2 -5

OUTPUT

4

Giải thích: Có ~4~ cách cắt:

Trong các cách cắt, cách cắt thứ ~1~ có chênh lệch nhỏ nhất giữa phần có giá trị lớn nhất và phần có giá trị nhỏ nhất: ~4~.

Trước khi bàn giao các robot tại công ty VBT, có ~N~ robot xếp thẳng hàng để chờ đến lượt kiểm tra hệ thống. Mỗi robot có chiều cao khác nhau (được tính bằng đơn vị đo riêng biệt).

Trong lúc chờ đợi, các robot có thể quét và nhận diện những robot quen biết xung quanh để trao đổi với nhau. Tuy nhiên, do cảm biến bị hạn chế, không phải robot nào cũng nhận diện được nhau.

Hai robot A và B đứng trong hàng có thể nhận diện được nhau nếu thỏa mãn một trong hai điều kiện sau:

• Robot A và robot B đứng ngay cạnh nhau trong hàng.
• Giữa robot A và robot B không có robot nào cao hơn hẳn một trong hai robot đó.

Yêu cầu

Đếm số cặp robot có thể nhận diện được nhau trong hàng.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~ là số lượng robot;
• ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương là chiều cao của một robot (tính theo đơn vị đo riêng biệt, giá trị không lớn hơn ~2 \times 10^9~).

Dữ liệu đầu ra

Ghi ra một số nguyên duy nhất là số cặp robot có thể nhận diện được nhau.

Ràng buộc dữ liệu

• Subtask 1: Có ít nhất 33% số test có ~N \le 100~;
• Subtask 2: Có ít nhất 50% số test có ~N \le 1000~;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
2
4
1
2
2

OUTPUT

6

Giải thích:

• Có ~4~ cặp robot thỏa mãn điều kiện thứ nhất: các cặp robot ở vị trí: ~(1, 2)~, ~(2, 3)~, ~(3, 4)~, ~(4, 5)~.
• Có ~2~ cặp robot thỏa mãn điều kiện thứ hai: các cặp robot ở vị trí ~(2, 4)~, ~(2, 5)~.

~\rightarrow~ Số cặp robot có thể nhận diện được nhau là ~6~.