TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

94.3% (33/35)

Submission's AC Ratio

46.0% (80/174)

Description

  在拜特嵐(Byteland)內有一條街,街上有n ≥ 3 棟民宅,每棟民宅前都種了一棵Dynamic
Tree(動態樹)。為什麼會叫動態樹呢,因為它們會一直動來動去,有時候會伸展(Splay)、有時
候會Link-Cut、甚至還會 Skip和Dancing。每個人都以門前的動態樹自豪,甚至還有動態樹的
世界排名(1 ≤ 名次 ≤ 100,000 且每個人皆相異)。

  俗語說『獨學無友,則孤陋寡聞』,所以他們常常辦 Party來互相切磋。每場 Party為期一
天,會由兩戶合辦,但是他們總是不會辦在自己家中,他們會選擇某一家地理位置位於兩戶之
間且動態樹世界排名也位於兩戶之間的民宅開Party。

有一天他們心血來潮,想知道如果每一種可能開 Party的組合都辦過,總共會花掉幾天?

(兩場 Party只要舉辦地點或是合辦的兩戶組合不一樣就算不一樣的 Party)

Input Format

對於 30% 測試資料,n ≤ 500
對於 60% 測試資料,n ≤ 5,000
對於100% 測試資料,n ≤ 50,000

輸入含多筆測試資料。
整個檔案的第一行有一個數字T(≤ 20),表示接下來有幾筆測試資料。
每筆測試資料包含兩行,第一行有一個數字n 表示民宅戶數。
第二行有n 個數字,依序表示每棟民宅的動態樹的世界排名

Output Format

對每筆測試資料輸出一行包含一個數字k,表示總共要花k 天。

Sample Input

2
3
1 2 3
4
1 3 2 4

Sample Output

1
2

Hints

對於第一筆測試資料,只有位置 (1,3) 合辦在2 一組 Party。
對於第二筆測試資料,有 (1,4) 合辦在3 跟 (1,4) 合辦在2 兩組 Party 情況。

Problem Source

原TIOJ1710 / 建國中學99年校內培訓contest #9 prob 1
source:ACM-ICPC Reginals Beijing 2008~2009

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6
6 2500 65536 262144 7
7 2500 65536 262144 8
8 2500 65536 262144 9
9 2500 65536 262144 10