#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/D

Repovive

Max by Min - Repovive Standard Round 1 (Sponsored by TIG Foundation) | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

4D. Max by Min

2000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given an array $a$ of length $n$ .

In one operation, you choose a segment $[l,r]$ with $1 \le l \le r \le n$ , and then for every index $i$ such that $l < i < r$ you set $a_i = \max\!\big(a_i,\ \min(a_l,\ a_r)\big)$ .

You may apply the operation any number of times (possibly zero). Your goal is to maximize the sum $\sum_{i=1}^{n} a_i$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

3
2
3 5

Case 1

5
4 1 1 1 3

Case 2

6
3 1 10 1 1 5

Explanation

Case 1

Scenario 1: Array: $[3, 5]$ . No interior positions exist (need $l < i < r$ , but only $2$ elements). No operations possible. Answer $= 3 + 5 = 8$ .

Case 2

Scenario 2: Array: $[4, 1, 1, 1, 3]$ . Operation on $[1, 5]$ : $\min(4, 3) = 3$ , raises all interior elements (indices $2, 3, 4$ ) from $1$ to $3$ . Final array: $[4, 3, 3, 3, 3]$ . Answer $= 4 + 3 + 3 + 3 + 3 = 16$ .

Case 3

Scenario 3: Array: $[3, 1, 10, 1, 1, 5]$ . Operation on $[3, 6]$ : $\min(10, 5) = 5$ , raises indices $4, 5$ from $1$ to $5$ . Operation on $[1, 3]$ : $\min(3, 10) = 3$ , raises index $2$ from $1$ to $3$ . Final array: $[3, 3, 10, 5, 5, 5]$ . Answer $= 3 + 3 + 10 + 5 + 5 + 5 = 31$ .

Output

Case 1

Case 2

Case 3

You are given an array $a$ of length $n$ .

In one operation, you choose a segment $[l,r]$ with $1 \le l \le r \le n$ , and then for every index $i$ such that $l < i < r$ you set $a_i = \max\!\big(a_i,\ \min(a_l,\ a_r)\big)$ .

You may apply the operation any number of times (possibly zero). Your goal is to maximize the sum $\sum_{i=1}^{n} a_i$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Scenario 1: Array: $[3, 5]$ . No interior positions exist (need $l < i < r$ , but only $2$ elements). No operations possible. Answer $= 3 + 5 = 8$ .