Trong một trận đấu bóng đá, người ta bán được ~N~ vé ~(N \le 3 \times 10^5)~. Mỗi khán giả có một vé, trên vé ghi số nguyên dương. Người ta muốn tặng quà cho những người có vé thuộc dãy số hạnh phúc. Dãy số hạnh phúc là một dãy số chỉ bao gồm các số hoàn thiện.

Số hoàn thiện được định nghĩa là một số mà có tổng các ước không kể nó bằng chính nó. Ví dụ: ~6~ có ~3~ ước thỏa mãn là ~1, 2, 3~ tổng các ước là ~6~.

Yêu cầu: Từ số vé ban đầu đã cho, em hãy tìm ra những người được tặng quà thỏa mãn yêu cầu trên.

Input

Vào từ tệp văn bản QUA.INP gồm:

• Dòng đầu tiên ghi số nguyên ~N~ là số lượng vé đã bán ~(1 \le N \le 3 \times 10^5)~.
• Dòng tiếp theo ghi ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~, ~(0 < A_i < 3 \times 10^5, i = 1, 2,\dots, N)~. Mỗi số cách nhau một khoảng trắng (dấu cách).

Output

Ghi ra file QUA.OUT gồm:

• Dòng đầu tiên là số lượng người được tặng quà. Nếu không có ai được tặng quà thì đưa ra số ~0~.
• Dòng thứ hai là số vé được tặng quà theo thứ tự xuất hiện trong dữ liệu vào, mỗi số cách nhau một dấu cách.

Sample Input 1

9
5 18 7 4 6 13 8 11 27

Sample Output 1

1
6

Bờm đi siêu thị, trong siêu thị có ~M~ loại màu bi khác nhau, loại bi màu ~i~ có ~a_i~ hộp, mỗi hộp có ~b_i~ viên bi. Giá mỗi hộp bi là như nhau. Bờm cần mua ~N~ hộp bi để tổng số bi trong ~N~ hộp là nhiều nhất.

Yêu cầu: Cho ~N~ là số hộp bi Bờm cần mua và ~M~ là số màu các hộp bi. Hãy lập trình giúp Bờm chọn ~N~ hộp bi sao cho tổng số bi mua được là nhiều nhất.

Input

Vào từ tệp văn bản CHONBI.INP:

• Dòng đầu tiên hai số ~N, M~ ~(N, M \leq 10^4)~.

• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~a_i~ và ~b_i~ ~(1 \leq a_i, b_i \leq 10^5)~.

• Dữ liệu vào đảm bảo luôn đủ ~N~ hộp để Bờm mua.

Output

Ghi ra file CHONBI.OUT:

• Một dòng gồm số lượng viên bi nhiều nhất trong ~N~ hộp Bờm mua được.

Sample Input 1

7 3
5 10
2 5
3 6

Sample Output 1

62

Dãy số ~b_1, b_2, ..., b_k~ được gọi là dãy đẹp nếu thỏa mãn điều kiện sau: với mỗi giá trị ~b_i~ trong dãy, số lần xuất hiện của nó trong dãy là đúng ~b_i~ lần.

Ví dụ: Dãy ~4, 4, 1, 2, 4, 2, 4~ là dãy đẹp vì giá trị ~4~ xuất hiện ~4~ lần, ~1~ xuất hiện ~1~ lần, ~2~ xuất hiện ~2~ lần. Dãy ~2, 5, 1, 2~ là không phải là dãy đẹp vì ~5~ xuất hiện ~1~ lần.

Yêu cầu: Cho dãy số nguyên gồm ~N~ phần tử ~a_1, a_2,….a_N~. Tìm số phần tử ít nhất cần xóa khỏi dãy để dãy trở thành dãy đẹp?

Input

Vào từ tệp văn bản DAYDEP.INP:

• Dòng 1 chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~)

• Dòng 2 chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~0 \leq a_i \leq 10^6~)

Output

Đưa ra tệp DAYDEP.OUT một số duy nhất là số lượng số ít nhất cần xóa để dãy trở thành dãy đẹp.

Sample Input 1

5
2 5 1 2 5

Sample Output 1

2

Notes

Giải thích : xóa ~2~ số ~5~ thì dãy còn ~3~ phần tử ~2, 1, 2~ là dãy đẹp

Để chuẩn bị cho kỳ thi học sinh giỏi tỉnh, thầy Minh muốn thành lập đội tuyển học sinh giỏi môn tin gồm ~3~ học sinh từ ~N~ học sinh, tên học sinh thứ ~i~ là ~S_i~. Vì các học sinh của thầy đều học giỏi nên thầy phải đưa ra điều kiện chọn đội như sau:

• Tên của mỗi học sinh được chọn phải bắt đầu bằng kí tự H, S, G, P, hoặc T.

• Tên các em học được chọn phải có chữ cái đầu đôi một khác nhau.

Yêu cầu: Em hãy viết chương trình cho biết thầy Minh có bao nhiêu cách chọn đội tuyển gồm ~3~ học sinh thoả mãn điều kiện trên.

Input

Vào từ tệp văn bản CHONDOI.INP:

• Dòng ~1~ chứa số nguyên dương ~N~ (~1 \le N \le 10^5~)

• ~N~ dòng sau, dòng thứ ~i~ là tên học sinh ~S_i~ (không có hai học sinh nào có tên giống nhau) có độ dài không quá ~10~ chỉ gồm các kí tự chữ cái in hoa.

Output

Đưa ra tệp CHONDOI.OUT một số nguyên là số các chọn ~3~ học sinh vào đội tuyển thoả mãn điều kiện trên.

Sample Input 1

5
HONG
SANG
GIANG
ANH
HANH

Sample Output 1

2

Notes

(Hai cách chọn 3 học sinh thoả mãn điều kiện: (HONG, SANG, GIANG); (SANG, GIANG, HANH))