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ẻ)</p>

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}