基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。

生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近, 因此在基因序列中的連續片段被認為是有意義的。

一個包含 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), 共四個。