TopCoder

User's AC Ratio

90.0% (18/20)

Submission's AC Ratio

37.5% (30/80)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 2500 65536
1 2500 65536
2 2500 65536
3 2500 65536
4 2500 65536
5 2500 65536
6 2500 65536
7 2500 65536
8 2500 65536
9 2500 65536