순열 패턴

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

요약

길이 n(50 이하)인 순열에서 231 패턴을 포함하지 않는 공백이 아닌 부분수열의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 재귀
정답자: 아직 제출이 없습니다

문제

서로 다른 $m$ 개의 수로 이루어진 수열 $a_1, \dots, a_m$ 에서 $1 \leq i < j < k \leq m$ 이고 $a_k < a_i < a_j$ 를 만족하는 $(i, j, k)$ 가 없으면, 이 수열을 "231이 없는 수열"이라고 한다. Bobo는 $1, \dots, n$ 의 순열 $p_1, \dots, p_n$ 을 가지고 있으며, 원소를 일부 제거할 수 있다(아무것도 제거하지 않아도 되지만 전부 제거할 수는 없다). 제거 후 남은 $(2^n - 1)$ 개의 순열 중에서 231이 없는 수열의 개수를 구하라.

입력

테스트 케이스가 여러 개 주어지며, 입력은 파일의 끝에서 끝난다. 각 테스트 케이스는 두 줄로 주어진다. 첫 줄에는 정수 $n$ 이 주어진다. 둘째 줄에는 정수 $p_1, \dots, p_n$ 이 주어진다.

출력

각 테스트 케이스마다 231이 없는 수열의 개수를 나타내는 정수를 한 줄에 출력한다.

제한

$1 \leq n \leq 50$ 이며, 각 $1 \leq i \leq n$ 에 대해 $1 \leq p_i \leq n$ 이다. 한 입력 파일에 포함된 $n$ 의 합은 500을 넘지 않는다.

예제1

예제 1
입력
```
2
2 1
3
1 2 3
4
2 3 4 1
```
예상 출력
```
3
7
11
```