English statement is here

Vì hâm mộ nhân vật siêu trộm Kid trong bộ truyện tranh Thám tử lừng danh Conan, Tèo đã nộp đơn xin gia nhập vào Tổ chức Siêu trộm quốc gia (NSTO). Tổ chức đã giao cho cậu một nhiệm vụ đầu tiên, nếu hoàn thành được, cậu chính thức được trở thành thành viên của tổ chức này. Nhiệm vụ của cậu là đột nhập vào phòng bảo mật và lấy được tập tài liệu bên trong két sắt. Tèo đã đột nhập thành công vào phòng bảo mật, bây giờ cậu cần nhập mật khẩu két sắt để có thể lấy được tài liệu. Cậu được tổ chức cung cấp dãy gồm ~n~ chữ số. Mật khẩu két sắt là một hoán vị của dãy số đó thỏa mãn không có ~2~ chữ số liên tiếp nào giống nhau. Tèo không còn cách nào khác phải liệt kê toàn bộ khả năng và thử nó. Bạn hãy giúp Tèo đếm xem có bao nhiêu mật khẩu thỏa mãn nhé.

Dữ liệu

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \le n \le 10)~
• Dòng tiếp theo chứa ~n~ chữ số ~a_i~ ~(0 \le a_i \le 9)~

Kết quả

• Một số nguyên duy nhất là số mật khẩu thỏa mãn.

Giới hạn

• Subtask ~1~ ~(15\%)~: số lượng các chữ số giống nhau trong dãy được cung cấp ~> \frac{n}{2}~.
• Subtask ~2~ ~(85\%)~: không có ràng buộc nào thêm.

Ví dụ ~1~

Dữ liệu

3
1 1 2

Kết quả

1

Giải thích

• Mật khẩu thỏa mãn là 1 2 1

Ví dụ ~2~

Dữ liệu

2
1 1

Kết quả

0

Giải thích

• Không có mật khẩu nào thỏa mãn.