Cho dãy số nguyên có n phần tử $a_1,a_2,...a_n$ bạn hãy lập trình đếm một số dữ liệu như sau:

Input

Dòng đầu chứa số nguyên dương n $(3<=n<=1000)$

Dòng tiếp theo chứa n số nguyên có giá trị tuyệt đối không vượt quá ${10}^4$

Output

Dòng đầu tiên là số lượng những số không chia hết cho 3 trong dãy

Dòng thứ hai là số lượng những Số chính phương trong dãy

Dòng thứ ba là số những cặp 2 số ở hai vị trí liên tiếp $a_i,a_{i+1}$ mà số sau chia hết cho số trước

Dòng thứ tư là những cặp 2 số ở vị trí bất kỳ khác nhau $a_i,a_j(1<=i<j<=n)$ mà cùng tính chẵn lẻ (chẵn cùng chẵn hoặc lẻ cùng lẻ)

Dòng thứ năm là số những bộ 3 số liên tiếp $a_{i-1},a_i,a_{i+1}$ tăng dần $a_{i-1}<a_i<a_{i+1}$

Ví dụ

Input

10
-1 2 -3 4 0 -5 6 -7 8 9

Output

6
3
2
20
1

Giải thích

Những số không chia hết cho 3 gồm -1,2,4,-5,-7,8

Những số chính phương gồm 0,4,9

Những cặp 2 số liên tiếp số sau chia hết cho số trước là {-1,2} và {4,0}

Những cặp cùng tính chẵn lẻ gồm {-1,-3},{-1,-5},{-1,-7},{-1,9}, {2,4},{2,0},{2,6},{2,8},{-3,-5},{-3,-7},{-3,9},{4,0},{4,6},{4,8},{0,6},{0,8},{-5,-7},{-5,9},{6,8},{-7,9}

Một bộ ba liên tiếp tăng là {-7,8,9}