回分類題庫
h061: E.檸檬汽水傳說?
關鍵字: NPSC 2009 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 22 Times / 21 Users | Submit : 78 Times / 32 Users | Accepted rate : 66%
題目加入時間 : 2012-11-04 02:08

Content: 简体中文

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

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

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

Input:

輸入資料第一行有一個數字表示測資有幾組。
之後每組測資有 2 行,第一行有一個整數 N ( 1 <= N < 1000000 ) 代表勇者的等級為 1 ~ N,第二行有 N 個數字,第 i 個數字 Ai 代表等級 i 的勇者所擁有的守護騎士的數量。
( 0 <= Ai < 2147483647 )

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
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 :

4
4
8
11

Hint :

Author :

NPSC 2009 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum