TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

92.4% (61/66)

Submission's AC Ratio

66.3% (116/175)

Description

基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近,因此在基因序列中的連續片段被認為是有意義的。一個包含$n$ 個基因的序列可以用 ${1, 2, \dots, n}$ 所組成的排列 $S= (s_1, s_2, \dots, s_n)$ 來表示。為了預測基因序列 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 \leq a < b \leq 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 \leq a < b \leq n$, 是一個框架區間?例如,在基因序列 $S = (2, 1, 5, 4, 3) $上,是框架區間的數對$ (a, b) , 1 \leq b \leq 5$, 有 $(1, 2)$、$(3, 4)$、$(3, 5)$ 和 $(4, 5)$,共四個。

Input Format

針對所輸入的基因序列$ S$,輸出一個數字,代表有多少數對$ (a, b),1 \leq a < b \leq 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 \leq20$、$1 \leq n \leq 100$。
第二組$30$ 分,所有的測資$T \leq 6$、$1 \leq n \leq 3000$。
第三組$40 $分,所有的測資$T\leq 20$、$1 \leq n \leq 5000$。

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 30
2 1~3 30
3 4 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 131072 262144 1
1 10000 131072 262144 2
2 10000 131072 262144 2
3 10000 131072 262144 2
4 10000 131072 262144 3