> For the complete documentation index, see [llms.txt](https://eaglepb2.gitbook.io/cpw/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://eaglepb2.gitbook.io/cpw/meta-coding-competitions/2011/round-1a/diversity-number.md).
# Diversity Number
https\://www\.facebook.com/codingcompetitions/hacker-cup/2011/round-1a/problems/A
## Question
Let's call a sequence of integers $$a\_1,a\_2,...,a\_N$$ *almost monotonic* if first K elements are non-decreasing sequence and last $$N-K+1$$ elements are non-increasing sequence: $$a\_1\le a\_2≤...≤a\_K$$ and $$a\_K≥a\_{K+1}≥...≥a\_N$$.
The *diversity number* of a sequence $$a\_1,a\_2,...,a\_N$$ is the number of possible sequences $$b\_1,b\_2,...,b\_N$$ for which $$0≤b\_i\**T**, the number of test cases. Each test case consists of a number **M**, the number of elements in a sequence, followed by **M** numbers **n**, elements of some sequence (note that this sequence is not necessarily *almost monotonic*). All tokens are whitespace-separated.
### Constraints
$$
T = 20
$$
$$
1 \le M, n \le 100
$$
### Output Format
Output T lines, with the answer to each test case on a single line.
### Sample Inputs:
{% tabs %}
{% tab title="Input 0" %}
#### Input
```
5
1
1
2
2 1
3
1 3 2
4
1 3 1 2
4
2 3 4 3
```
#### Output
```
2
5
15
17
80
```
{% endtab %}
{% endtabs %}
***
Solution