동물원

시간 제한2초메모리 제한512 MB

요약

각 동물이 보고한 같은 종 중 자신보다 큰 동물 수가 어떤 서로 다른 키 순서로 실현되도록 N마리를 두 종으로 나누는 경우의 수를 센다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

동물원에 동물이 $N$ 마리 있고, 1번부터 $N$ 번까지 번호가 매겨져 있다. 동물원에는 토끼와 고양이만 있고, 모든 동물의 키는 서로 다르다.

수빈이는 토끼와 고양이를 구분하지 못하지만, 동물과 대화할 수 있다. 수빈이는 모든 동물에게 이렇게 물었다.

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

토끼는 모두 자신보다 키가 큰 토끼의 수를 답했고, 고양이는 모두 자신보다 키가 큰 고양이의 수를 답했다.

1번 동물부터 $N$ 번 동물까지의 대답이 주어진다. 각 동물이 토끼인지 고양이인지 정하는 방법이 몇 가지인지 구하라. 동물 한 마리라도 종류가 다르면 서로 다른 방법으로 센다. 키는 주어지지 않으므로, $N$ 마리의 키를 서로 다르게 정해서 주어진 대답을 그대로 만들 수 있으면 그 방법은 가능한 방법이다. 토끼가 한 마리도 없어도 되고, 고양이가 한 마리도 없어도 된다.

입력

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

둘째 줄에 1번 동물부터 $N$ 번 동물까지의 대답이 공백으로 구분되어 주어진다. 각 대답은 $0$ 이상 $40$ 이하의 정수이다.

출력

첫째 줄에 가능한 방법의 수를 출력한다.

예제5

예제 1
입력
```
5
0 1 2 3 4
```
예상 출력
```
2
```
예제 2
입력
```
2
5 8
```
예상 출력
```
0
```
예제 3
입력
```
6
0 0 0 0 0 0
```
예상 출력
```
0
```
예제 4
입력
```
5
1 0 2 0 1
```
예상 출력
```
8
```
예제 5
입력
```
3
1 0 1
```
예상 출력
```
0
```