{"raw_statement":[{"iden":"statement","content":"There are n cities in Regularia, Alice's homeland. They are located at the vertices of a regular n-gon. The cities are numbered from 1 to n in a clockwise order (see the figure).\n\nThe people of Regularia love Alice so much that they made her the queen of the country. Alice wants to prove herself, so she has ordered a construction of a new highway system connecting cities of Regularia. Alice has come up with a plan to build the highways, which is an n-permutation p1, p2, ..., pn. Specifically, for a city numbered i, Alice wants to build a highway between the cities i and pi, where pi is the number of some other city. A highway is a straight line connecting two cities. According to Alice's plan, any two cities will be connected by no more than a single highway.\n\nOf course, some of the highways may intersect one another. Two highways are said to intersect if and only if there is a unique point that belongs to both of the highways and is not a city. This point is called a #cf_span(class=[tex-font-style-underline], body=[junction]) of the two highways. Even if more than two highways meet at a single point, each pair has its own separate junction. As a complicated and expensive interchange has to be built at each junction, Alice is interested in the total number of junctions in her plan. Help her find this number!\n\nFor example, the plan for a permutation 4, 1, 5, 3, 2 is shown in the figure. \n\nThe first line contains a single integer n, the number of cities in Regularia (3 ≤ n ≤ 105). The next line contains n space-separated integers p1, p2, ..., pn, which is a permutation of length n. It is guaranteed that i ≠ pi for any i and that no two cities will be connected by more than a single highway.\n\nOutput a single integer — the total number of junctions in Alice's plan.\n\nA #cf_span(class=[tex-font-style-underline], body=[permutation]) of length n is any rearrangement of the sequence 1, 2, ..., n.\n\n"},{"iden":"input","content":"The first line contains a single integer n, the number of cities in Regularia (3 ≤ n ≤ 105). The next line contains n space-separated integers p1, p2, ..., pn, which is a permutation of length n. It is guaranteed that i ≠ pi for any i and that no two cities will be connected by more than a single highway."},{"iden":"output","content":"Output a single integer — the total number of junctions in Alice's plan."},{"iden":"examples","content":"Input54 1 5 3 2Output2Input64 5 6 3 1 2Output6"},{"iden":"note","content":"A #cf_span(class=[tex-font-style-underline], body=[permutation]) of length n is any rearrangement of the sequence 1, 2, ..., n."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 10^5 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $ such that $ p_i \\neq i $ for all $ i $.  \nCities are labeled $ 1 $ to $ n $ and placed in clockwise order on a regular $ n $-gon.  \nFor each $ i \\in \\{1, \\dots, n\\} $, a highway is drawn as a straight line segment between city $ i $ and city $ p_i $.\n\n**Constraints**  \n1. $ p_i \\neq i $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. Each pair of cities is connected by at most one highway (i.e., the mapping $ i \\mapsto p_i $ is a permutation, so each edge $ (i, p_i) $ is undirected and unique).  \n\n**Objective**  \nCompute the total number of **junctions**, defined as intersection points of two highways that are **not** cities.  \nTwo highways $ (i, p_i) $ and $ (j, p_j) $ intersect (at a junction) if and only if their line segments cross in the interior of the polygon, i.e., they form a crossing chord pair.\n\n**Key Geometric Insight**  \nIn a convex $ n $-gon, two chords $ (i, p_i) $ and $ (j, p_j) $ intersect **if and only if** the four endpoints are distinct and appear in alternating order around the polygon. That is, without loss of generality, the four indices $ i, j, p_i, p_j $ are distinct and appear in cyclic order as $ i, j, p_i, p_j $ (or any cyclic rotation thereof) such that the chords cross.\n\nThus, the number of junctions equals the number of unordered pairs $ \\{i, j\\} $ with $ i < j $ such that the four points $ i, p_i, j, p_j $ are distinct and form a crossing pair.\n\n**Formal Objective**  \nCount the number of unordered pairs $ \\{i, j\\} $ with $ 1 \\leq i < j \\leq n $ such that the chords $ (i, p_i) $ and $ (j, p_j) $ intersect, i.e., the four indices $ i, j, p_i, p_j $ are distinct and appear in alternating cyclic order around the polygon.\n\nThis is equivalent to:  \n$$\n\\boxed{\n\\sum_{1 \\leq i < j \\leq n} \\mathbf{1}_{\\text{chords } (i,p_i) \\text{ and } (j,p_j) \\text{ intersect}}\n}\n$$","simple_statement":"Alice is queen of Regularia, where n cities are placed in a circle, numbered 1 to n clockwise. She connects each city i to city p[i], forming n straight highways. Two highways intersect if they cross at a point that is not a city. Count the total number of such crossing points (junctions).","has_page_source":false}