Một trạm thu nhận được một mảng chứa 2N + 2 tín hiệu. Trong đó, có N loại tín hiệu xuất hiện lặp lại đúng 2 lần, và chỉ có đúng 2 loại tín hiệu quan trọng xuất hiện duy nhất 1 lần. Hãy sử dụng thuật toán với độ phức tạp thời gian O(N) và bộ nhớ O(1) để tìm ra giá trị của 2 tín hiệu quan trọng đó. (In ra theo thứ tự giá trị từ nhỏ đến lớn).

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5). (Tổng số phần tử là 2N+2).

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

Output: Hai số nguyên xuất hiện 1 lần, cách nhau bởi khoảng trắng, số nhỏ in trước.

Ví dụ:

Input:

2
4 1 2 1 2 5

Output:

4 5

Một địa chỉ IPv4 hợp lệ gồm 4 số nguyên (mỗi số từ 0 đến 255) phân cách nhau bởi dấu chấm, và các số không được chứa số 0 vô nghĩa ở đầu (ví dụ 01 là không hợp lệ, nhưng 0 thì hợp lệ). Do lỗi đường truyền, các dấu chấm trong địa chỉ IP đã bị mất, chỉ còn lại một xâu ký tự toàn chữ số S. Hãy tính xem có bao nhiêu địa chỉ IP hợp lệ có thể được tạo ra từ xâu S ban đầu bằng cách chèn 3 dấu chấm vào.

Input: Một xâu chữ số S (Độ dài <= 20).

Output: Số lượng địa chỉ IPv4 hợp lệ.

Ví dụ:

Input:

25525511135

Output:

2

(Giải thích: 255.255.11.135 và 255.255.111.35).

Trên một con phố có N tòa nhà xếp thành một hàng ngang, tòa nhà thứ i có chiều cao là H_i. Một người đứng ở nóc tòa nhà thứ i và nhìn về phía bên phải. Tầm nhìn của họ sẽ liên tục bao quát được các tòa nhà bên phải cho đến khi bị chặn bởi một tòa nhà có chiều cao lớn hơn hoặc bằng chiều cao tòa nhà i. Với mỗi tòa nhà, hãy đếm số lượng tòa nhà nằm trong tầm nhìn của nó.

Input:

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

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

Output: In ra N số, số thứ i là số lượng tòa nhà nhìn thấy từ tòa nhà i.

Ví dụ:

Input:

6
10 3 7 4 1 2

Output:

5 0 3 1 1 0

(Giải thích: Tòa nhà 1 cao 10, cao hơn tất cả nên nhìn được cả 5 tòa bên phải. Tòa nhà 3 cao 7 nhìn được 4, 1, 2 nên là 3).

Một dãy gồm N đống quặng kim loại được xếp thành hàng ngang, đống thứ i có khối lượng W_i. Bạn cần gộp tất cả chúng lại thành 1 đống duy nhất. Mỗi lần gộp, bạn chỉ được phép gộp 2 đống quặng nằm kề nhau thành 1 đống mới, và chi phí cho lần gộp đó bằng tổng khối lượng của 2 đống quặng. Hãy tìm cách gộp sao cho tổng chi phí của tất cả các lần gộp là nhỏ nhất.

Input:

Dòng 1: N (1 <= N <= 400).

Dòng 2: N số nguyên Wi (1 <= Wi <= 100).

Output: Tổng chi phí nhỏ nhất.

Ví dụ:

Input:

4
1 3 5 2

Output:

22

(Giải thích: Gộp 1+3=4 (chi phí 4). Dãy còn: 4 5 2. Gộp 5+2=7 (chi phí 7). Dãy còn: 4 7. Gộp 4+7=11 (chi phí 11). Tổng chi phí = 4 + 7 + 11 = 22).