TopCoder

$\Huge Kzzz$
$\text{\Huge \color{black}假\color{red}裝自己是紅黑}$

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

63.0% (17/27)

Tags

Description

在心跳加速空間裡,有很多個勇者,每個勇者都能夠召喚數量不等的守護騎士。而這些勇者因為打敗大邪神油膩膩及妖神頌五力而被國王阿拉拉可拉拉優酪乳三世給予不同的等級,分別為等級 $1$ 到等級 $N$ ,每個等級都會有一個勇者。

不同的勇者之間會互相的溝通,當等級 $i$ 的勇者要和等級 $j$ 勇者溝通的時候,若存在一個等級 $k$ 的勇者, $k$ 介於 $i,j$ 之間,且這個等級 $k$ 勇者擁有比等級 $i$ 的勇者或等級 $j$ 的勇者的守護騎士多的時候,這個等級 $k$ 的勇者就會去阻止他們的溝通。

給定各個等級勇者的守護騎士數量。請問能夠互相溝通的配對 $(i,j)$ 共有幾組。

Input Format

輸入的第一行有一個數字 $T(T \leq 10)$ 表示測資有幾組。之後每組測資有 $2$ 行,第一行有一個整數 $N(1\leq N < 10^6)$ 代表勇者的等級為 $1\sim N$ ,第二行有 $N$ 個數字,第 $i$ 個數字 $A_i$ 代表等級 $i$ 的勇者所擁有的守護騎士的數量。

$0\leq A_i < 2147483647$

Output Format

每組測資輸出一行表示能夠互相溝通的勇者配對共有幾組。

Sample Input 1

4
4
1 2 2 3
4
3 2 2 1
5
5 3 1 3 5
6
5 3 1 1 3 5

Sample Output 1

4
4
8
11

Hints

Problem Source

NPSC
NEOJ Problem 22

Subtasks

No. Testdata Range Constraints Score
1 0~10 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 131072 65536 1
1 3000 131072 65536 1
2 3000 131072 65536 1
3 3000 131072 65536 1
4 3000 131072 65536 1
5 3000 131072 65536 1
6 3000 131072 65536 1
7 3000 131072 65536 1
8 3000 131072 65536 1
9 3000 131072 65536 1
10 3000 131072 65536 1