Một số nguyên dương ~n~ được gọi là số tốt nếu thỏa mãn điều kiện:

• Tồn tại chính xác một cặp số nguyên ~(x, y)~ sao cho ~0 < x < y~ và ~x^2 + y^2 = n~.

Ví dụ, với ~n = 2026~ thì chỉ có duy nhất ~(x, y) = (1, 45)~ thỏa ~0 < x < y~ và ~x^2 + y^2 = 2026~, nên ~2026~ là một số tốt.

Yêu cầu

Cho số nguyên dương ~N~. Hãy liệt kê tất cả các số tốt không vượt quá ~N~ theo thứ tự tăng dần.

Dữ liệu

Gồm một dòng chứa số nguyên ~N~.

Kết quả

Gọi có ~k~ số tốt không vượt quá ~N~, và dãy các số đó theo thứ tự tăng dần là ~(a_1, a_2, \dots, a_k)~.

Hãy in ra:

• Dòng 1: ~k~
• Dòng 2: ~a_1~ ~a_2~ ~\dots~ ~a_k~ (cách nhau bởi dấu cách). Nếu ~k = 0~ thì dòng 2 là dòng trống.

Ví dụ

Ví dụ 1

Input

10

Output

2
5 10

Ví dụ 2

Input

1

Output

0

Ví dụ 3

Input

50

Output

14
5 10 13 17 20 25 26 29 34 37 40 41 45 50

Giải thích

Ví dụ 1

• ~5~ là số tốt vì chỉ có ~(x, y) = (1, 2)~ thỏa ~x^2 + y^2 = 5~.
• ~10~ là số tốt vì chỉ có ~(x, y) = (1, 3)~ thỏa ~x^2 + y^2 = 10~. Không có số tốt nào khác không vượt quá ~10~.

Ví dụ 2

Không tồn tại số tốt nào không vượt quá ~1~, nên ~k = 0~ và dòng 2 để trống.

Ví dụ 3

Có ~14~ số tốt không vượt quá ~50~, được liệt kê đúng như output.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^7~
• ~N~ là số nguyên
• Các số trên cùng một dòng cách nhau bởi một dấu cách

Chấm điểm

• Subtask1 ~(70\%)~ điểm: ~1 \le N \le 2 \times 10^5~
• Subtask2 ~(30\%)~ điểm: Không có ràng buộc bổ sung.

Cho dãy số nguyên ~A=(A_1,A_2,\dots,A_N)~. Ta gọi một bộ ba chỉ số ~(i,j,k)~ là hợp lệ nếu tỉ lệ giá trị tại các vị trí đó tạo thành ~7:5:3~, và chỉ số ~j~ nằm ở một đầu trong ba chỉ số.

Yêu cầu

Hãy đếm số bộ ba ~(i,j,k)~ thỏa mãn đồng thời:

• ~1 \le i,j,k \le N~
• ~A_i : A_j : A_k = 7:5:3~
• ~\min(i,j,k)=j~ hoặc ~\max(i,j,k)=j~

Dữ liệu

• Dòng 1: Số nguyên ~N~
• Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~

Kết quả

In ra một số nguyên là số bộ ba ~(i,j,k)~ thỏa điều kiện.

Ví dụ

Ví dụ 1

Input

10
3 10 7 10 7 6 7 6 5 14

Output

7

Ví dụ 2

Input

6
210 210 210 210 210 210

Output

0

Ví dụ 3

Input

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Output

34

Giải thích

Ví dụ 1

Có đúng ~7~ bộ ba thỏa điều kiện.

Mỗi bộ ba đều có ~A_i:A_j:A_k=7:5:3~, đồng thời ~j~ là chỉ số nhỏ nhất hoặc lớn nhất trong ~{i,j,k}~: ~(3,9,1)~ ~(5,9,1)~ ~(7,9,1)~ ~(10,2,6)~ ~(10,2,8)~ ~(10,4,6)~ ~(10,4,8)~

Ví dụ 2

Mọi phần tử đều bằng nhau nên không thể có tỉ lệ ~7:5:3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 3 \times 10^5~
• ~1 \le A_i \le 10^9~
• Tất cả dữ liệu vào là số nguyên
• Các số trên cùng một dòng cách nhau bởi một dấu cách

Chấm điểm

• Subtask1 ~(50\%)~ điểm: ~1 \le N \le 4000~
• Subtask2 ~(30\%)~ điểm: ~1 \le N \le 3 \times 10^5~, ~1 \le A_i \le 2 \times 10^6~
• Subtask3 ~(20\%)~ điểm: Không có ràng buộc bổ sung.

Có ~N~ người (đánh số từ ~1~ đến ~N~) đứng dọc theo bờ sông. Ta xét hệ trục tọa độ 2D, trong đó trục ~x~ là dọc theo sông và trục ~y~ là chiều cao.

Người ~i~ đứng tại điểm ~(A_i,0)~ và muốn thả diều tại điểm ~(B_i,1)~. Khi đó dây diều của người ~i~ là đoạn thẳng nối hai điểm ~(A_i,0)~ và ~(B_i,1)~.

Để tránh va chạm và rối dây, hai người ~i~ và ~j~ (với ~i \ne j~) không thể thả diều cùng lúc nếu hai đoạn thẳng tương ứng có điểm chung, kể cả trường hợp chỉ chạm nhau tại đầu mút.

Yêu cầu

Hãy tìm số người lớn nhất có thể thả diều đồng thời sao cho mọi cặp dây diều trong nhóm đều không có giao điểm.

Dữ liệu

• Dòng 1: số nguyên ~N~
• ~N~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~A_i~ và ~B_i~

Kết quả

In ra một số nguyên là số người lớn nhất có thể thả diều đồng thời.

Ví dụ

Ví dụ 1

Input

3
3 5
1 4
2 6

Output

2

Ví dụ 2

Input

5
1 2
1 3
1 4
1 5
1 6

Output

1

Ví dụ 3

Input

10
440423913 766294629
725560240 59187619
965580535 585990756
550925213 623321125
549392044 122410708
21524934 690874816
529970099 244587368
757265587 736247509
576136367 993115118
219853537 21553211

Output

4

Giải thích

Ví dụ 1

Chọn người ~1~ và ~2~ (hoặc ~2~ và ~3~) thì hai dây không cắt nhau, nhưng nếu chọn cả ~1,2,3~ thì dây của ~1~ và ~3~ sẽ cắt nhau, nên đáp án là ~2~.

Ví dụ 2

Tất cả đều có ~A_i=1~ nên mọi dây đều chung điểm ~(1,0)~ (chạm đầu mút), do đó chỉ chọn được tối đa ~1~ người.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 2 \times 10^5~
• ~0 \le A_i \le 10^9~
• ~0 \le B_i \le 10^9~
• Mọi giá trị vào đều là số nguyên
• Các số trên cùng một hàng cách nhau ít nhất bởi một dấu cách.

Chấm điểm

• Subtask1 ~(70\%)~ điểm: ~1 \le N \le 2000~
• Subtask2 ~(30\%)~ điểm: Không có ràng buộc bổ sung.

Một dãy số ~a=(a_1,a_2,\dots,a_k)~ (với ~k~ bất kỳ) được gọi là Kado như sau:

• Gọi ~x~ là số lượng chỉ số nguyên ~i~ thỏa ~2 \le i \le k-1~, ~a_{i-1} < a_i~ và ~a_i > a_{i+1}~.
• Gọi ~y~ là số lượng chỉ số nguyên ~i~ thỏa ~2 \le i \le k-1~, ~a_{i-1} > a_i~ và ~a_i < a_{i+1}~.
• Dãy ~a~ được gọi là Kado khi và chỉ khi ~x > y~.

Cho một hoán vị ~P~ của ~(1,2,\dots,N)~. Hãy đếm số dãy con (không nhất thiết liên tiếp) của ~P~ là Kado, lấy modulo ~998244353~.

Yêu cầu

Tính số lượng dãy con của ~P~ thỏa tính chất Kado, lấy phần dư khi chia cho ~998244353~.

Dữ liệu

• Dòng 1: số nguyên ~N~
• Dòng 2: ~N~ số nguyên ~P_1,P_2,\dots,P_N~ (là một hoán vị của ~(1,2,\dots,N)~)

Kết quả

In ra một số nguyên là đáp án modulo ~998244353~.

Ví dụ

Ví dụ 1

Input

4
1 3 4 2

Output

4

Ví dụ 2

Input

1
1

Output

0

Ví dụ 3

Input

20
11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3

Output

431610

Giải thích

Ví dụ 1

Có đúng ~4~ dãy con Kado: ~(1,3,4,2)~, ~(1,3,2)~, ~(1,4,2)~, ~(3,4,2)~.

Ví dụ 3

Ví dụ dãy con ~(10,13,12,5,7,9,20,3)~ là Kado.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 3 \times 10^5~
• ~P~ là hoán vị của ~(1,2,\dots,N)~
• Các số trên cùng một dòng cách nhau bởi một dấu cách.

Chấm điểm

• Subtask1 ~(50\%)~ điểm: ~1 \le N \le 5000~
• Subtask2 ~(30\%)~ điểm: ~1 \le N \le 10^5~
• Subtask3 ~(20\%)~ điểm: Không có ràng buộc bổ sung