TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

93.2% (41/44)

Submission's AC Ratio

72.1% (80/111)

Description

基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近,因此在基因序列中的連續片段被認為是有意義的。一個包含n 個基因的序列可以用 {1, 2, …, n} 所組成的排列 S= (s1, s2, ..., sn) 來表示。為了預測基因序列 S 上可能有意義的片段,一位生物學家遭遇了下列問題。令 F(a, b) 代表在基因序列 S 上位置落在基因a 和基因b 之間的所有整數所構成的集合 (含a 和 b)。例如,令 S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9, 11, 10, 12, 3),則F(6, 8) = F(8, 6) = {6, 4, 14, 13, 5, 8}。令 I(a, b) 代表數線上 a 和 b 這兩個整數間所有整數所構成的集合 (含a 和 b)。例如,I(6, 8) = I(8, 6) = {6, 7, 8}。在基因序列 S上如果兩個整數 a 和 b , 1 ≤ a < b ≤ n, 滿足F(a, b) = I(a, b) 則稱 (a, b) 構成一個「框架區間」 (framed interval)。舉例來說,考慮基因序列 S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9,11, 10, 12, 3),以 (a, b) = (9, 12) 為例,因為 F(9, 12) = {9, 11, 10, 12} = {9, 10, 11, 12}= I(9, 12),所以 (9, 12) 是一個框架區間。相同的 (6, 7)、(10, 11) 和 (13, 14) 也是框架區間。
這位生物學家想知道給定一個基因序列 S,有多少數對 (a, b) , 1 ≤ a < b ≤ n, 是一個框架區間?例如,在基因序列 S = (2, 1, 5, 4, 3) 上,是框架區間的數對 (a, b) , 1 ≤a < b ≤ 5, 有 (1, 2)、(3, 4)、(3, 5) 和 (4, 5),共四個。

Input Format

針對所輸入的基因序列 S,輸出一個數字,代表有多少數對 (a, b),1 ≤ a < b ≤n, 是一個框架區間?

Output Format

Sample Input

輸入範例1:
3
4
3 1 4 2
4
3 2 1 4
5
2 1 5 4 3

輸入範例2:
2
14
2 7 6 4 14 13 5 8 1 9 11 10 12 3
11
3 10 4 5 6 8 7 9 11 2 1

Sample Output

輸出範例1:
0
3
4

輸出範例2:
4
9

Hints

本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組30 分,所有的測資T ≤ 20、1 ≤ n ≤ 100。
第二組30 分,所有的測資T ≤ 6、1 ≤ n ≤ 3000。
第三組40 分,所有的測資T ≤ 20、1 ≤ n ≤ 5000。

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第三題
Set by Paupière

Subtasks

For Testdata: 0 ~ 0, Score: 30
For Testdata: 1 ~ 3, Score: 30
For Testdata: 4 ~ 4, Score: 40
No. Time Limit (ms) Memory Limit (KiB)
0 10000 131072
1 10000 131072
2 10000 131072
3 10000 131072
4 10000 131072