{"raw_statement":[{"iden":"statement","content":"A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fixed point.\n\nA derangement is a permutation without any fixed points.\n\nLet's denote the operation swap(a, b) as swapping elements on positions a and b.\n\nFor the given permutation find the minimal number of swap operations needed to turn it into derangement.\n\nThe first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation.\n\nThe second line contains the elements of the permutation — n distinct integers from 1 to n.\n\nIn the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement.\n\nIn each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations.\n\nIf there are multiple possible solutions, output any of them.\n\n"},{"iden":"input","content":"The first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation.The second line contains the elements of the permutation — n distinct integers from 1 to n."},{"iden":"output","content":"In the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement.In each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations.If there are multiple possible solutions, output any of them."},{"iden":"examples","content":"Input66 2 4 3 5 1Output12 5"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 200000 $.  \nLet $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nA *fixed point* is an index $ i $ such that $ \\pi_i = i $.  \nA *derangement* is a permutation with no fixed points.\n\n**Constraints**  \n- $ \\pi $ is a bijection from $ \\{1, \\dots, n\\} $ to $ \\{1, \\dots, n\\} $.  \n- The goal is to transform $ \\pi $ into a derangement using the minimum number of transpositions (swaps).\n\n**Objective**  \nFind the minimum number $ k $ of swap operations $ \\text{swap}(a_i, b_i) $ such that the resulting permutation $ \\pi' $ satisfies $ \\pi'_i \\neq i $ for all $ i \\in \\{1, \\dots, n\\} $, and output the sequence of swaps achieving this minimum.","simple_statement":"Find the minimum number of swaps to turn a permutation into a derangement (no element stays in its original position). Output the number of swaps and the swap pairs.","has_page_source":false}