{"raw_statement":[{"iden":"statement","content":"The construction of subway in Bertown is almost finished! The President of Berland will visit this city soon to look at the new subway himself.\n\nThere are _n_ stations in the subway. It was built according to the _Bertown Transport Law_:\n\n1.  For each station _i_ there exists exactly one train that goes from this station. Its destination station is _p__i_, possibly _p__i_ = _i_;\n2.  For each station _i_ there exists exactly one station _j_ such that _p__j_ = _i_.\n\nThe President will consider the _convenience_ of subway after visiting it. The _convenience_ is the number of ordered pairs (_x_, _y_) such that person can start at station _x_ and, after taking some subway trains (possibly zero), arrive at station _y_ (1 ≤ _x_, _y_ ≤ _n_).\n\nThe mayor of Bertown thinks that if the subway is not _convenient_ enough, then the President might consider installing a new mayor (and, of course, the current mayor doesn't want it to happen). Before President visits the city mayor has enough time to rebuild some paths of subway, thus changing the values of _p__i_ for **not more than two subway stations**. Of course, breaking the _Bertown Transport Law_ is really bad, so the subway must be built according to the _Law_ even after changes.\n\nThe mayor wants to do these changes in such a way that the _convenience_ of the subway is maximized. Help him to calculate the maximum possible _convenience_ he can get!"},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 100000) — the number of stations.\n\nThe second line contains _n_ integer numbers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — the current structure of the subway. All these numbers are distinct."},{"iden":"output","content":"Print one number — the maximum possible value of _convenience_."},{"iden":"examples","content":"Input\n\n3\n2 1 3\n\nOutput\n\n9\n\nInput\n\n5\n1 5 4 3 2\n\nOutput\n\n17"},{"iden":"note","content":"In the first example the mayor can change _p_2 to 3 and _p_3 to 1, so there will be 9 pairs: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3).\n\nIn the second example the mayor can change _p_2 to 4 and _p_3 to 5."}],"translated_statement":[{"iden":"statement","content":"伯特own的地铁建设已接近完成！伯兰总统即将访问该市，亲自查看新地铁。\n\n地铁共有 #cf_span[n] 个车站，其建设遵循《伯特own交通法》：\n\n总统在参观后将评估地铁的“便利性”。所谓“便利性”，是指有序对 #cf_span[(x, y)] 的数量，使得乘客可以从车站 #cf_span[x] 出发，乘坐若干班地铁列车（可能为零）后到达车站 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]）。\n\n伯特own市长认为，如果地铁的“便利性”不够高，总统可能会考虑更换市长（当然，现任市长不希望发生这种情况）。在总统到访前，市长有足够时间重建部分地铁线路，从而最多修改两个车站的 #cf_span[pi] 值。当然，破坏《伯特own交通法》是严重违规行为，因此即使修改后，地铁仍必须符合该法律。\n\n市长希望在满足上述约束的前提下，使地铁的“便利性”最大化。请帮助他计算所能达到的最大“便利性”值！\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——车站数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[p1], #cf_span[p2], ..., #cf_span[pn]（#cf_span[1 ≤ pi ≤ n]）——当前地铁结构。所有这些数字互不相同。\n\n输出一个数——“便利性”的最大可能值。\n\n在第一个示例中，市长可以将 #cf_span[p2] 改为 #cf_span[3]，将 #cf_span[p3] 改为 #cf_span[1]，从而得到 #cf_span[9] 对：#cf_span[(1, 1)], #cf_span[(1, 2)], #cf_span[(1, 3)], #cf_span[(2, 1)], #cf_span[(2, 2)], #cf_span[(2, 3)], #cf_span[(3, 1)], #cf_span[(3, 2)], #cf_span[(3, 3)]。\n\n在第二个示例中，市长可以将 #cf_span[p2] 改为 #cf_span[4]，将 #cf_span[p3] 改为 #cf_span[5]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——车站数量。第二行包含 #cf_span[n] 个整数 #cf_span[p1], #cf_span[p2], ..., #cf_span[pn]（#cf_span[1 ≤ pi ≤ n]）——当前地铁结构。所有这些数字互不相同。"},{"iden":"output","content":"输出一个数——“便利性”的最大可能值。"},{"iden":"examples","content":"输入32 1 3输出9输入51 5 4 3 2输出17"},{"iden":"note","content":"在第一个示例中，市长可以将 #cf_span[p2] 改为 #cf_span[3]，将 #cf_span[p3] 改为 #cf_span[1]，从而得到 #cf_span[9] 对：#cf_span[(1, 1)], #cf_span[(1, 2)], #cf_span[(1, 3)], #cf_span[(2, 1)], #cf_span[(2, 2)], #cf_span[(2, 3)], #cf_span[(3, 1)], #cf_span[(3, 2)], #cf_span[(3, 3)]。在第二个示例中，市长可以将 #cf_span[p2] 改为 #cf_span[4]，将 #cf_span[p3] 改为 #cf_span[5]。"}],"sample_group":[],"show_order":[],"formal_statement":"### Definitions\n\n*   Let $n \\in \\mathbb{Z}_{\\ge 1}$ be the number of stations.\n*   Let $V = \\{1, 2, \\dots, n\\}$.\n*   Let $S_n$ be the set of all permutations of $V$.\n*   The input specifies an initial permutation $P \\in S_n$, defined by the sequence $(p_1, p_2, \\dots, p_n)$.\n*   For any permutation $\\pi \\in S_n$, let $G_\\pi$ be the directed graph with vertices $V$ and edges $E_\\pi = \\{(i, \\pi_i) \\mid i \\in V\\}$.\n*   Let $\\mathcal{C}_\\pi$ be the set of disjoint cycles in $G_\\pi$. For a cycle $C \\in \\mathcal{C}_\\pi$, let $|C|$ denote the number of vertices in that cycle.\n*   The **convenience** function $W: S_n \\to \\mathbb{Z}$ is defined as:\n    $$W(\\pi) = \\sum_{C \\in \\mathcal{C}_\\pi} |C|^2$$\n\n### Optimization Problem\n\n**Objective:**\nMaximize $W(Q)$\n\n**Subject to:**\n1.  $Q \\in S_n$\n2.  $|\\{i \\in V \\mid p_i \\neq Q_i\\}| \\le 2$\n\n**Output:**\nThe maximum possible value of $W(Q)$.","simple_statement":null,"has_page_source":false}