← 返回题目列表

Codeforces · 884/C

C. 伯敦地铁

中文机器翻译题面 查看原题

Bertown地铁建设即将完工!贝尔兰总统很快将访问这座城市,亲自参观新地铁。

地铁有n个车站。它是根据伯敦运输法建造的:

1. 对于每个车站 i,恰好存在从该车站出发的一列火车。其目的站为pi,可能pi = i;
2. 对于每个站点 i,恰好存在一个站点 j,使得 pj = i。

总统参观后会考虑地铁的便利性。便利性是有序对 (x, y) 的数量,使得人们可以从车站 x 出发,乘坐一些地铁列车(可能为零)后到达车站 y (1 ≤ x, y ≤ n)。

伯敦市长认为,如果地铁不够方便,那么总统可能会考虑任命一位新市长(当然,现任市长不希望这种情况发生)。在总统访问之前,市长有足够的时间重建一些地铁路径,从而改变不超过两个地铁站的 pi 值。当然,违反《伯敦交通法》确实很糟糕,所以即使修改后,地铁也必须按照该法建设。

市长希望以最大限度地提高地铁便利性的方式进行这些改变。帮他计算一下他能获得的最大可能的便利!

输入

第一行包含一个整数 n (1 ≤ n ≤ 100000) — 站点数量。

第二行包含 n 个整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 地铁的当前结构。所有这些数字都是不同的。

输出

打印一个数字 — 方便的最大可能值。

示例

输入 #1

3
2 1 3

输出 #1

9

输入 #2

5
1 5 4 3 2

输出 #2

17

注意

在第一个示例中,市长可以将 p2 更改为 3,将 p3 更改为 1,因此将有 9 对:(1, 1)、(1, 2)、(1, 3)、(2, 1)、(2, 2)、(2, 3)、(3, 1)、(3, 2)、(3, 3)。

在第二个示例中,市长可以将 p2 更改为 4,将 p3 更改为 5。