Minimum Awards Distribution

Emma is tasked with distributing awards to her students based on their ratings. She must follow these rules:

• Every student must receive at least one award.
• If a student has a higher rating than an adjacent student, then that student must receive more awards than the adjacent student.

Your task is to determine the minimum total number of awards Emma must distribute for each test case.

The problem can be formulated as follows:
Given a list of ratings \(a_1, a_2, \dots, a_n\), assign awards \(w_1, w_2, \dots, w_n\) such that:

[ \begin{cases} w_i \ge 1, & 1 \le i \le n, \ a_i > a_{i-1} \implies w_i > w_{i-1}, & 2 \le i \le n, \ a_i > a_{i+1} \implies w_i > w_{i+1}, & 1 \le i \le n-1. \end{cases} ]

Compute \(\sum_{i=1}^{n} w_i\) minimizing the total awards.

inputFormat

The input will be given via standard input (stdin) and is formatted as follows:

t
n1
rating11 rating12 ... rating1n1
n2
rating21 rating22 ... rating2n2
...
nt
ratingt1 ratingt2 ... ratingtn_t

Where t denotes the number of test cases. For each test case, the first line contains an integer n representing the number of students, followed by a line with n space-separated integers representing the students' ratings.

outputFormat

For each test case, output the minimum total number of awards that must be distributed. Each result should be printed on a new line via standard output (stdout).

## sample

3
3
1 0 2
4
1 2 2 1
5
1 2 3 2 1

5
6
9

</p>