저울

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

요약

무게추 n개를 하나씩 접시에 올리면서 어느 순간에도 왼쪽 접시가 오른쪽보다 무겁지 않도록 놓는 방법의 수를 구한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 백트래킹, 재귀, 조합론
정답자: 아직 제출이 없습니다

문제

양팔 저울과 서로 다른 무게를 가진 $n$ 개의 추 $a_1, a_2, \ldots, a_n$ 이 주어진다. 주어진 추를 하나씩 차례로 저울 위에 올려놓되, 어느 순간에도 왼쪽 접시가 오른쪽 접시보다 무거워지지 않도록 해야 한다. 각 단계에서는 아직 올려놓지 않은 추 하나를 골라 왼쪽 접시 또는 오른쪽 접시에 올려놓는다. 모든 추를 사용할 때까지 이 과정을 반복한다. 이렇게 할 수 있는 방법의 수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $n$ 이 주어진다 ( $0 < n < 10$ ). 둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $0 < a_1, a_2, \ldots, a_n < 1000$ ).

출력

방법의 수를 나타내는 정수 하나를 출력한다.

예제1

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