Cho một dãy gồm N số nguyên dương a1, a2, .... aN.

Hãy in ra số lượng phần tử trong dãy là số chính phương. Một số nguyên dương x được gọi là số chính phương nếu tồn tại một số nguyên dương k sao cho k^2 = x.

Input:

Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 10^5).

Dòng thứ hai chứa N số nguyên dương a1, a2, ..., aN (1 ≤ ai ≤ 10^9, 1 ≤ i ≤ N).

Output:

In ra số lượng số chính phương trong dãy.

Subtasks:

• 40% số test có ràng buộc bổ sung: N ≤ 100, ai ≤ 100 (1 ≤ i ≤ N).

• 60% số test còn lại không có ràng buộc bổ sung.

Ví dụ:

Input:

5
1 4 7 16 10

Output:

3

Giải thích: Có 3 số chính phương: 1, 4, 16.

Bạn có N lá bài đặt thành một hàng, lá bài thứ i có giá trị ai. Bạn chơi trò chơi sau:

• Trong mỗi lượt, lấy hai lá bài ở đầu hàng bên trái ra so sánh giá trị.

• Nếu một lá bài có giá trị lớn hơn, lá lớn hơn này được đặt lại vào đầu hàng, lá nhỏ hơn bị loại bỏ.

• Nếu hai lá bài có giá trị bằng nhau, cả hai đều bị loại bỏ.

Lặp lại cho đến khi còn tối đa 1 lá bài.

Hãy in ra giá trị của lá bài còn lại cuối cùng. Nếu không còn lá bài nào, in ra 0.

Input:

Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 10^6).

Dòng thứ hai chứa N số nguyên dương a1, a2, ..., aN (1 ≤ ai ≤ 10^9, 1 ≤ i ≤ N).

Output:

In ra một số nguyên duy nhất: giá trị lá bài còn lại, hoặc 0 nếu không còn lá nào.

Subtasks:

• 40% số test có ràng buộc bổ sung: N ≤ 10^3.

• 60% số test còn lại không có ràng buộc bổ sung.

Ví dụ:

Input 01:

5
3 1 4 1 5

Output 01:

5

Giải thích:

Lượt 1: so 3 và 1 → 3 lớn hơn, hàng: [3, 4, 1, 5]

Lượt 2: so 3 và 4 → 4 lớn hơn, hàng: (4, 1, 5]

Lượt 3: so 4 và 1 → 4 lớn hơn, hàng: [4, 5]

Lượt 4: so 4 và 5 → 5 lớn hơn, hàng: [5]

Còn lại: 5.

Input 02:

4
2 2 3 3

Output 02:

0

Giải thích:

Lượt 1: so 2 và 2 → bằng, loại cả hai, hàng: [3, 3]

Lượt 2: so 3 và 3 → bằng, loại cả hai, hàng: []

Không còn lá nào → 0.

Bạn cần lát đầy dải ô vuông kích thước 1xN bằng các viên gạch có độ dài 1, 2, hoặc 3.

• Gạch có độ dài 1 có a màu khác nhau.

• Gạch có độ dài 2 có b màu khác nhau.

• Gạch có độ dài 3 có c màu khác nhau.

Hai cách lát được coi là khác nhau nếu tồn tại ít nhất một ô vuông kích thước 1x1 mà viên gạch phủ trên đó khác nhau về độ dài hoặc màu sắc.

Hãy đếm số cách lát đầy dải 1xN, kết quả lấy dư cho 998244853.

Input:

Dòng duy nhất chứa bốn số nguyên dương N, a, b, c (1 ≤ N ≤ 10^6, 1 ≤ a, b, c ≤ 10^9).

Output:

In ra một số nguyên duy nhất: số cách lát dải, lấy dư cho 998244853.

Subtasks:

• 50% số test khác có ràng buộc bổ sung: N ≤ 10^3.

• 50% số test còn lại không có ràng buộc bổ sung.

Ví dụ:

Input:

3 2 1 1

Output:

13

Giải thích:

Ba gạch độ dài 1: 2^3 = 8 cách.

Gạch độ dài 1 + gạch độ dài 2: 2x1 = 2 cách.

Gạch độ dài 2 + gạch độ dài 1: 1x2 = 2 cách.

Một gạch độ dài 3: 1 cách.

Tổng = 8 + 2 + 2 + 1 = 13.

Trường H tổ chức chương trình tuyển chọn học sinh cho đội tuyển chuyên. Có 2026 chuyên đề kiến thức được đánh số thứ tự từ 1 đến 2026. Hội đồng chuyên môn xác định M chuyên đề trọng tâm, trong đó K chuyên đề đầu tiên được xem là các chuyên đề cốt lõi quan trọng nhất.

Mỗi học sinh đăng ký đúng K chuyên đề mà mình tự tin nhất (các chuyên đề đôi một khác nhau). Dựa trên mức độ phù hợp giữa lựa chọn của học sinh và danh sách chuyên đề trọng tâm, hội đồng phân loại học sinh theo các nhóm năng lực sau (ưu tiên nhóm có số thứ tự nhỏ nhất mà học sinh đạt được):

• Nhóm năng lực 1: Toàn bộ K chuyên đề đăng ký đều nằm trong K chuyên đề cốt lõi.

• Nhóm năng lực 2: Toàn bộ K chuyên đề đăng ký đều nắm trong M chuyên đề trọng tâm.

• Nhóm năng lực 3: Có thể chọn ra K - 1 chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc K - 1 chuyên đề cốt lõi đầu tiên.

• Nhóm năng lực 4: Có thể chọn ra K - 1 chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc K chuyên đề cốt lõi.

• Nhóm năng lực 5: Có thể chọn ra K - 1 chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc M chuyên đề trọng tâm.

• Nhóm năng lực 6: Có thể chọn ra K - 2 chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc M chuyên đề trọng tâm.

Có J học sinh tham gia đăng ký. Mỗi học sinh được xếp vào nhóm năng lực có số thứ tự nhỏ nhất mà học sinh đó thỏa mãn điều kiện.

Viết một chương trình để xác định:

• Nhiệm vụ 1 : Số lượng học sinh được xếp vào nhóm năng lực C cụ thể. Các nhóm năng lực được đánh số 1,2,..., 6, 7. Nhóm năng lực 7 dành cho những học sinh không thuộc nhóm nào ở trên.

• Nhiệm vụ 2 : Các chuyên đề nhiều học sinh đăng ký nhất, được viết theo thứ tự tăng dần nếu có nhiều hơn 1 chuyên đề thỏa mãn.

Input:

Dòng đầu tiên ghi mã số nhiệm vụ (1 hoặc 2).

Dòng thứ hai ghi 3 số M, K, C (1 ≤ M ≤ 2026, 5 ≤ K ≤ M, 1 ≤ C ≤ 7).

Dòng thứ ba ghi số thứ tự M chuyên đề trọng tâm, theo thứ tự ưu tiên (cốt lỗi trước, mở rộng sau).

Dòng thứ tư ghi một số tự nhiên J (1 ≤ J ≤ 5 x 10^4), biểu thị số lượng học sinh và mỗi dòng trong số J dòng tiếp theo ghi K số tự nhiên, biểu thị các chuyên đề mà học sinh đó đăng ký.

Output:

Đối với nhiệm vụ 1, in ra số lượng học sinh thuộc nhóm năng lực C.

Đối với nhiệm vụ 2, in ra số thứ tự các chuyên đề được nhiều học sinh đăng ký nhất, viết theo thứ tự tăng dần.

Subtasks:

50% số test có K ≤ 10^4,J ≤ 2 x 10^4.

50% còn lại không có ràng buộc gì thêm.

Ví dụ:

Input:

1
6 5 1
11 12 13 14 15 16
1
15 14 13 12 11

Output:

1

Giải thích:

Nhiệm vụ 1. Hội đồng xác định 6 chuyên đề trọng tâm theo thứ tự là 11,12,13,14,15,16. Mỗi học sinh đăng ký 5 chuyên đề. Có một học sinh duy nhất. Học sinh này đăng ký các chuyên đề 15,14,13,12,11. Học sinh được xếp vào Nhóm 1 vì đã đăng ký đúng 5 chuyên đề cốt lỗi đầu tiên.

Input 02:

1
6 5 4
21 22 23 24 25 26
2
29 21 25 23 22
23 21 25 22 24

Output 02:

2

Phòng máy có N chiếc máy tính, máy thứ i đang chạy ở xung nhịp A_i. Để thiết lập mạng máy tính song song, bạn cần đưa xung nhịp của tất cả N máy về CÙNG MỘT mức. Mỗi thao tác, bạn được phép chọn 1 máy tính và tăng hoặc giảm xung nhịp của nó đi 1 đơn vị. Hãy tính số thao tác ít nhất để đồng bộ toàn bộ N máy tính.

Input:

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

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

Output: Số thao tác ít nhất.

Ví dụ:

Input:

3
1 2 9

Output:

8

(Giải thích: Đồng bộ tất cả về mức 2. Máy 1 tăng 1, máy 2 không đổi, máy 3 giảm 7. Tổng số thao tác = 1 + 0 + 7 = 8).