저울

양팔 저울과 서로 다른 무게를 가진 $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$).

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