408353: GYM103104 D Fragmentation merging

Yesterday is Monday, you have to attend the operating system class at 8:00 a.m. Sadly, you were so tired that you got up late and you didn't arrive at the class in time. So you decided to learn this class in your bed. In your dream, you have a memory space, which is a permutation of length $$$n$$$, where the i-th element is $$$a_i$$$.

In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing capacity or performance and often both. The exact consequences of fragmentation depend on the specific system of storage allocation in use and the particular form of fragmentation. In many cases, fragmentation leads to storage space being wasted.

We call a pair $$$(l,r)$$$ satisfying $$$1 \leq l,r \leq n$$$ as a fragmentation. If $$$l \leq r$$$, this fragmentation contains elements $$$a_l$$$ … $$$a_r $$$ (including $$$a_l$$$ and $$$a_r$$$ themselves). At this time, this fragmentation can be regarded as a set contains $$$r-l+1$$$ elements. Otherwise, this fragmentation can be regarded as an empty set.

The most severe problem caused by fragmentation is causing a process or system to fail, due to premature resource exhaustion. In order to avoid this, the allocator may, instead of failing, trigger a defragmentation (or memory compaction cycle) or other resource reclamation, such as a major garbage collection cycle, in the hope that it will then be able to satisfy the request.

We define that if and only if any two fragmentations (which can be empty) meet the following conditions, then they can be merged. For the set $$$A$$$ and $$$B$$$ formed by any two fragmentations, let $$$C=A \cup B$$$, the largest element in $$$C$$$ is $$$c_{max}$$$, and the smallest element in $$$C$$$ is $$$c_{min}$$$(If $$$C$$$ is an empty set, then $$$c_{max}=c_{min}=0$$$), the number of elements in $$$C$$$ is exactly equal to $$$c_{max}-c_{min}+1$$$, and $$$A \cap B= \varnothing$$$. We call the merged set $$$C$$$ a super-fragmentation. Notice that a super-fragmentation is a set, not a pair.

For example, for memory space $$$[1,2,4,3,5]$$$,

We define that fragmentation $$$(1,3)$$$ and fragmentation $$$(4,4)$$$ are mergeable, because set $$$\{1,2,4\}$$$ $$$\cup$$$ set $$$\{3\}$$$ have $$$4$$$ elements, which are exactly equal to $$$4-1+1$$$, and set $$$\{1,2,4\}$$$ $$$\cap$$$ set $$$\{3\}$$$ $$$= \varnothing$$$.

Fragmentation $$$(1,2)$$$ and fragmentation $$$(3,3)$$$ can't be merged, because set $$$\{1,2\}$$$ $$$\cup$$$ set $$$\{4\}$$$ have $$$3$$$ elements, not equal to $$$4-1+1$$$.

Fragmentation $$$(1,3)$$$ and fragmentation $$$(2,4)$$$ can't be merged, because set $$$\{1,2,4\}$$$ $$$\cap$$$ set $$$\{2,4,3\}$$$ $$$\neq \varnothing$$$.

Now you want to know the number of super-fragmentations of different specifications can be obtained for arbitrarily selected two fragmentations. Formally, you need to calculate the number of sets $$$C$$$, which exists two fragmentations $$$A$$$, $$$B$$$, their combine result is $$$C$$$.

Notice that two sets $$$A$$$, $$$B$$$ is the same if and only if $$$A\subseteq B$$$ and $$$B\subseteq A$$$.

In order to simplify the problem, you only need to consider one merging, which means the super-fragmentation obtained after merging will not be merged with any fragmentation or super-fragmentation again.

There are multiple test cases. The first line of the input contains an integer $$$T(1\leq T\leq 10^4)$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$($$$1 \leq n \leq 5000$$$), indicating the length of the permutation.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$, indicating the permutation in order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

For each test case, output the number of different kinds of super-fragmentation you can get in one line.

2
1
1
5
1 2 4 3 5

0
15