Permutation Pattern

Time limit2sMemory limit1024 MB

Summary

Given a permutation of length n (n up to 50), count the non-empty subsequences that avoid the 231 pattern.

Level: Hard8 of 10
Topics: Dynamic programming, Recursion
Solved: No attempts yet

Problem

A sequence $a_1, \dots, a_m$ of $m$ distinct numbers is called "without 231" if there is no triple $(i, j, k)$ with $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 elements from it (possibly none, but not all). Find the number of sequences without 231 among the $(2^n - 1)$ resulting permutations.

Input

The input consists of several test cases, and the input ends at end-of-file. Each test case has two lines. The first line contains an integer $n$ . The second line contains $n$ integers $p_1, \dots, p_n$ .

Output

For each test case, output one integer, the number of sequences without 231.

Constraints

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

Examples1

Example 1
Input
```
2
2 1
3
1 2 3
4
2 3 4 1
```
Expected output
```
3
7
11
```