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。