Пекка развлекается

면접 대비

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지 번호가 적힌 카드를 나열할 때, k+1번 카드가 k번 카드보다 뒤에 오도록 하는 서로 다른 배열의 수를 센다. 카드 수는 최대 100이다.

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

문제

최근에 Пек카는 새로운 놀이를 시작했다. 그는 숫자 1이 적힌 똑같은 카드 $A_1$ 장, 숫자 2가 적힌 카드 $A_2$ 장, $\dots$ , 숫자 $N$ 이 적힌 카드 $A_N$ 장을 가지고 있다. 페카는 모든 카드를 한 줄로 나열해서, 만들어진 수열에서 $k>0$ 인 모든 숫자 $k+1$ 카드 앞에 숫자 $k$ 카드가 적어도 하나 있는 경우의 수를 알고 싶어한다. 페카를 도와주세요.

입력

첫 번째 줄에는 자연수 $N$ 이 주어진다. 두 번째 줄에는 $N$ 개의 공백으로 구분된 자연수 $A_1, A_2, \dots, A_N$ 이 주어진다. 모든 $A_i$ 의 합은 $100$ 을 넘지 않는다.

출력

문제의 조건에 맞는 카드 배열의 서로 다른 경우의 수를 출력한다.

힌트

예제에서 가능한 배열은 1 1 2 2, 1 2 1 2, 1 2 2 1이며, 총 세 가지 배열이 있다.

예제1

예제 1
입력
```
2
2 2
```
예상 출력
```
3
```