시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB106033327831.061%

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

5
0 1 2 3 4

예제 출력 1

2

예제 입력 2

2
5 8

예제 출력 2

0

예제 입력 3

6
0 0 0 0 0 0

예제 출력 3

0

예제 입력 4

5
1 0 2 0 1

예제 출력 4

8

예제 입력 5

3
1 0 1

예제 출력 5

0

출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: jh05013