31119번 - Permutation Pattern 다국어

문제

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ドル$.

노트