- Prepare
- Algorithms
- Dynamic Programming
- Counting Special Sub-Cubes

# Counting Special Sub-Cubes

# Counting Special Sub-Cubes

Given an *cube*, let (where ) denote the value stored in cell .

A *sub-cube* (where ) of an cube is considered to be *special* if the maximum value stored in any cell in the sub-cube is equal to .

For each in the inclusive range , calculate the number of special sub-cubes. Then print each as a single line of space-separated integers (i.e., ).

**Input Format**

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

- The first line contains an integer, , denoting the side length of the initial cube.
- The second line contains space-separated integers describing an array of integers in the form . The integer in some cell is calculated using the formula .

**Constraints**

- where

**Output Format**

For each query, print space-separated integers where the integer denotes the number of special sub-cubes for .

**Sample Input**

```
2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2
```

**Sample Output**

```
7 1
6 1
```

**Explanation**

We must perform the following queries:

We have a cube of size and must calculate the number of special sub-cubes for the following values of :

- : There are sub-cubes of size and seven of them have a maximum value of written inside them. So, for , the answer is .
- : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

We then print the respective values for each as a single line of space-separated integers (i.e.,

`7 1`

).We have a cube of size and must calculate the number of special sub-cubes for the following values of :

- : There are sub-cubes of size and six of them have a maximum value of written inside them. So, for , the answer is .
- : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

We then print the respective values for each as a single line of space-separated integers (i.e.,

`6 1`

).