Bạn được cho một danh sách gồm ~n~ số nguyên và nhiệm vụ của bạn là tính toán số lượng giá trị phân biệt trong danh sách.

Input

• Dòng đầu vào đầu tiên có một số nguyên ~n~: số lượng giá trị.
• Dòng tiếp theo chứa ~n~ số tự nhiên ~x_1, x_2, x_3, \ldots ,x_n~

Output

• In một số nguyên: số lượng giá trị phân biệt.

Constraints

• ~1 \leq n \leq 2 * 10^5~.
• ~1 \leq x_i \leq 10^9~.

Sample Test

Input:

5
2 3 2 2 3

Output:

2

Cho một dãy gồm ~n~ số, hãy tìm số trung vị của dãy.

Số trung vị là số đứng chính giữa dãy sau khi đã sắp xếp theo thứ tự tăng dần.

Ví dụ: ~arr[5] = [1, 3, 4, 5, 2]~ có mảng được sắp xếp là ~arr'[5] = [1, 2, 3, 4, 5]~ nên số trung vị sẽ là ~3~

Input

• Dòng đầu tiên chứa số tự nhiên lẻ ~n~.
• Dòng thứ hai chứa ~n~ số tự nhiên ~a_1, a_2,..., a_n~.

Output

• In ra số cần tìm.

Constraints

• ~1 \leq n \leq 10^6~.
• ~|a_i| \leq 10^4~.

Sample Test

Cho dãy số nguyên ~N~ số ~a_{1}, a_{2}, a_{3}, \ldots, a_{n}~.

Yêu cầu: Hãy tìm ~i < j~ để tích ~S=a_{i} \times a_{j}~ đạt giá trị lớn nhất.

Input

• Dòng đầu tiên chứa số tự nhiên ~N~.
• Dòng tiếp theo chứa ~N~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~.

Output

• In ra tích ~S~ lớn nhất có thể tìm được.

Constraints

• ~1 \leq N \leq 2 \times 10^5~.
• ~1 \leq |a_{i}| \leq 10^6~.

Sample Test

Input:

4
0 2 3 -1

Output:

6

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, \ldots, A_N~. Giá trị của dãy ~A~ được định nghĩa là tổng của ~|A_i - A_{i - 1}|~ với ~1 < i \leq N~.

Một hoán vị của dãy ~A~ là một dãy chứa các phần tử của dãy ~A~ theo thứ tự bất kì.

Xét tất cả hoán vị của dãy ~A~, hãy đưa ra giá trị của dãy nhỏ nhất có thể tìm được.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~N \leq 10^5~).
• Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~|A_i| \leq 10^9~).

Output

• In ra giá trị nhỏ nhất của một hoán vị của dãy ~A~.

Sample Test

Input:

4
1 5 2 4

Output:

4

Mrtee có ~N~ lớp, lớp thứ ~i~ cần ~n_{i}~ đề. Đồng thời, Mrtee có ~M~ trợ giảng và người thứ ~i~ sẽ tốn ~m_{i}~ tiền để ra một đề duy nhất. Tìm số tiền ít nhất mà Mrtee phải trả.

Lưu ý: mỗi trợ giảng chỉ ra đề cho ~1~ lớp.

Input

• Dòng đầu tiên chứa số tự nhiên ~N~.
• Dòng thứ hai chứa ~N~ số tự nhiên ~n_1, n_2, n_3, \ldots, n_N~ là số lượng đề mỗi lớp.
• Dòng thứ ba chứa số tự nhiên ~M~.
• Dòng thứ tư chứa ~M~ số tự nhiên ~m_1, m_2, m_3, \ldots, m_M~ là số tiền cần trả mỗi trợ giảng.

Output

• In ra số tiền ít nhất.

Constraints

• ~1 \leq N \leq M \leq 10^5~.
• ~1 \leq n_{i}, m_{i} \leq 10^5~.

Sample Test

Input:

3
1 2 3
4
9 2 5 10

Output:

25

Trong kì thi học sinh giỏi, mrtee phải chuẩn bị ~N~ máy tính cho ~N~ học sinh tham gia dự thi. ~N~ máy tính được xếp thẳng hàng nhau trên trục hoành của trục số, máy thứ ~i~ có toạ độ ~x_i~. Khoảng cách của hai máy ~i~ và ~j~ được tính là ~|x_i - x_j|~. Để đảm bảo nghiêm túc trong thi cử, thầy giáo muốn đặt một camera quan sát học sinh thẳng hàng với các máy trên sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Yêu cầu: Hãy giúp thầy giáo xác định số vị trí đặt camera sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Input

• Dòng đầu tiên chứ số nguyên dương ~N~ (~N \leq 10^6~).
• Dòng thứ hai gồm ~N~ số nguyên ~x_1, x_2, \ldots, x_N~ - toạ độ các máy tính (~|x_i| \leq 10^9~).

Output

• Dòng đâu tiên in ra số ~K~ - số vị trí đặt camera thoả mãn.
• Dòng thứ hai in ra các toạ độ đặt thoả mãn được sắp theo thứ tự tăng dần, cách nhau ít nhất một khoảng trắng.

Subtasks

• ~50\%~ số test ứng với ~N \leq 10^3~.
• ~50\%~ số test ứng với ~N \leq 10^5~.

Sample Test

Input:

6
3 1 7 2 5 7

Output:

3
3 4 5

Bạn được cho thời gian đến và rời đi của ~N~ khách hàng trong một nhà hàng.

Số lượng khách hàng tối đa trong nhà hàng bất cứ lúc nào là bao nhiêu?

Input

• Dòng đầu tiên chứa số tự nhiên ~N~.
• ~N~ dòng tiếp theo biểu diễn mỗi khách hàng. Mỗi dòng chứa 2 số nguyên ~a~ và ~b~: Thời gian đến và đi của thực khách đó.

Đảm bảo rằng tất cả thời gian đến và đi là khác nhau.

Output

• In ra số cần tìm.

Constraints

• ~1 \leq N \leq 2 \times 10^5~.
• ~1 \leq a < b \leq 10^9~.

Sample Test

Một số ~X~ ban đầu được tách thành ~N~ số ~A_1, A_2, \ldots, A_n~. Hãy tìm cách ghép lại ~N~ số này, theo thứ tự bất kỳ, thành số lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 100~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số ~A_i~ (độ dài số ~A_i~ không vượt quá ~100~). Lưu ý, ~A_i~ có thể có các chữ số ~0~ đứng ở đầu.

Output

• In ra số lớn nhất có thể tạo được từ việc ghép ~N~ số đã cho. Số này có thể có các chữ số ~0~ đứng ở đầu.

Sample Test

Input:

4
2
20
004
66

Output:

66220004

Xét tập ~F(N)~ tất cả các số hữu tỉ trong đoạn ~[0, 1]~ với mẫu số không quá ~N~.

Ví dụ, tập ~F(5)={\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}}~

Hãy tìm phân số thứ ~K~ trong tập ~F(N)~.

Input

Một dòng duy nhất chứa hai số ~N~ và ~K~ ~(1 < N \leq1000)~

Output

Ghi ra phân số thứ ~K~ tìm được theo định dạng trong ví dụ. Dữ liệu đảm bảo tồn tại phân số thứ ~K~.

Sample Test

Input:

5 3

Output:

1/4