在心跳加速空間裡,有很多個勇者,每個勇者都能夠召喚數量不等的守護騎士。而這些勇者因為打敗大邪神油膩膩及妖神頌五力而被國王阿拉拉可拉拉優酪乳三世給予不同的等級,分別為等級 $1$ 到等級 $N$ ,每個等級都會有一個勇者。
不同的勇者之間會互相的溝通,當等級 $i$ 的勇者要和等級 $j$ 勇者溝通的時候,若存在一個等級 $k$ 的勇者, $k$ 介於 $i,j$ 之間,且這個等級 $k$ 勇者擁有比等級 $i$ 的勇者或等級 $j$ 的勇者的守護騎士多的時候,這個等級 $k$ 的勇者就會去阻止他們的溝通。
給定各個等級勇者的守護騎士數量。請問能夠互相溝通的配對 $(i,j)$ 共有幾組。
輸入的第一行有一個數字 $T(T \leq 10)$ 表示測資有幾組。之後每組測資有 $2$ 行,第一行有一個整數 $N(1\leq N < 10^6)$ 代表勇者的等級為 $1\sim N$ ,第二行有 $N$ 個數字,第 $i$ 個數字 $A_i$ 代表等級 $i$ 的勇者所擁有的守護騎士的數量。
$0\leq A_i < 2147483647$
每組測資輸出一行表示能夠互相溝通的勇者配對共有幾組。
NPSC
NEOJ Problem 22
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~10 | 100 |