1719 測資加強 已 rejudge
1710 . Dynamic Tree
TopCoder
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 1
2
3
1 2 3
4
1 3 2 4
3
1 2 3
4
1 3 2 4
Sample Output 1
1
2
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 |