시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB111100.000%

문제

A sequence $a_1, \dots, a_m$ of $m$ distinct numbers is called *without 231* if there is **no** triples $(i, j, k)$ where $1 \leq i < j < k \leq m$ and $a_k < a_i < a_j$.

Bobo has a permutation $p_1, \dots, p_n$ of $1, \dots, n$, and he can remove some (possibly none, but not all) elements from the permutation. Find the number of sequences without $231$ among $(2^n - 1)$ resulting permutations.

입력

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains an integer $n$.

The second line contains $n$ integers $p_1, \dots, p_n$.

출력

For each test case, output an integer which denotes the number of sequences.

제한

  • $1 \leq n \leq 50$
  • $1 \leq p_i \leq n$ for each $1 \leq i \leq n$
  • In each input, the sum of $n$ does not exceed $500$.

예제 입력 1

2
2 1
3
1 2 3
4
2 3 4 1

예제 출력 1

3
7
11