12907번 - 동물원

동물원에 동물이 N마리 있고, 1번부터 N번가지 번호가 매겨져 있다. 이 동물원에 동물은 토끼나 고양이밖에 없고, 모든 동물의 키는 다 다르다.

수빈이는 토끼와 고양이를 구분할 수 없지만, 토끼와 고양이와 대화를 할 수 있다!

수빈이는 모든 동물에게 다음과 같은 질문을 했다.

"너랑 같은 동물 중에서 너보다 키가 큰 동물은 몇 마리야?"

모든 토끼는 자신보다 키가 큰 토끼의 수를 말해줬고, 모든 고양이도 자신보다 키가 큰 고양이의 수를 말해줬다.

모든 동물의 대답이 주어졌을 때, 각 대답을 어떤 동물이 했는지 알아내려고 한다. 가능한 조합의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 동물의 수 N (1 ≤ N ≤ 40)이 주어진다.

둘째 줄에는 각 동물의 대답이 주어진다. 대답은 0보다 크거나 같고, 40보다 작거나 같은 정수이다.

첫째 줄에 가능한 조합의 수를 출력한다.