TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

57.1% (4/7)

Submission's AC Ratio

17.2% (5/29)

Tags

Description

"嗚啊啊啊啊~~~"

房間魔王發出震耳欲聾的伸吟.

魔王的身體碎塊發出激烈的強光, 然後從房裡消逝.

身負重傷的妁艷, 搖搖擺擺地走向眼前的大門.

打開了大門, 這是一個監獄樣子的房間.

向遠處一望, 有個著制服的女孩的身影被關在牢中.

近前一看, 是妁艷的妹妹!

妹妹似乎注意到了房門打開的聲音, 抬起頭, 看到了妁艷.

"嗚..., 哥哥!", 妹妹眼框瞬間紅了起來.

兩人重逢了.

但是眼前的牢門之鎖隔開了兩人.

門鎖是由兩個正N邊形組成, 一個在內側一個在外側, 妁艷站在外側.

在兩個N邊形的頂點之間會有一些線, 其中一側的一個頂點必然恰好會連到另一側的其中一個頂點.(它們呈現一一對應)

經過仔細的觀察.

每一道機關都是N邊形的三個頂點, 逆時針方向的一個三角形, 且其內側對應的三角形也是逆時針方向.

必須將所有這樣的三角形都解開, 門鎖才會打開.

妁艷想知道自己要解多久, 有多少三角形的機關要解開.

Input Format

第一行有一個數字N (3 ≤ N ≤ 300,000), 意義如上文所述.

接下來有一行, 一共有N個數字, 為1~N的一個排列. 第i個數字ai代表外側的第i個頂點對應到內側的第ai個頂點. 編號由逆時針方向為1~N.

Output Format

輸出唯一的數字, 代表有幾個機關要解.

Sample Input 1

5
1 3 4 2 5

Sample Output 1

6

Hints

所有機關的內側對應編號: (1, 3, 4), (1, 3, 5), (1, 4, 5), (1, 2, 5), (3, 4, 2), (3, 4, 5) 共六組.

Problem Source

原TIOJ1773 / problem setter: willyliu

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 65536 262144 1
1 6000 65536 262144 2
2 6000 65536 262144 3
3 6000 65536 262144 4
4 6000 65536 262144 5
5 6000 65536 262144 6
6 6000 65536 262144 7
7 6000 65536 262144 8