{"raw_statement":[{"iden":"statement","content":"You are given a sequence of _n_ positive integers _d_1, _d_2, ..., _d__n_ (_d_1 < _d_2 < ... < _d__n_). Your task is to construct an undirected graph such that:\n\n*   there are exactly _d__n_ + 1 vertices;\n*   there are no self-loops;\n*   there are no multiple edges;\n*   there are no more than 106 edges;\n*   its _degree set_ is equal to _d_.\n\nVertices should be numbered 1 through (_d__n_ + 1).\n\n_Degree sequence_ is an array _a_ with length equal to the number of vertices in a graph such that _a__i_ is the number of vertices adjacent to _i_\\-th vertex.\n\n_Degree set_ is a sorted in increasing order sequence of all distinct values from the _degree sequence_.\n\nIt is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than 106 edges.\n\nPrint the resulting graph."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 300) — the size of the degree set.\n\nThe second line contains _n_ integers _d_1, _d_2, ..., _d__n_ (1 ≤ _d__i_ ≤ 1000, _d_1 < _d_2 < ... < _d__n_) — the degree set."},{"iden":"output","content":"In the first line print one integer _m_ (1 ≤ _m_ ≤ 106) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than 106 edges.\n\nEach of the next _m_ lines should contain two integers _v__i_ and _u__i_ (1 ≤ _v__i_, _u__i_ ≤ _d__n_ + 1) — the description of the _i_\\-th edge."},{"iden":"examples","content":"Input\n\n3\n2 3 4\n\nOutput\n\n8\n3 1\n4 2\n4 5\n2 5\n5 1\n3 2\n2 1\n5 3\n\nInput\n\n3\n1 2 3\n\nOutput\n\n4\n1 2\n1 3\n1 4\n2 3"}],"translated_statement":[{"iden":"statement","content":"你被给定一个由 #cf_span[n] 个正整数组成的序列 #cf_span[d1, d2, ..., dn] (#cf_span[d1 < d2 < ... < dn])。你的任务是构造一个无向图，满足以下条件：\n\n顶点编号应为 #cf_span[1] 到 #cf_span[(dn + 1)]。\n\n_度序列_ 是一个长度等于图中顶点数的数组 #cf_span[a]，其中 #cf_span[ai] 表示与第 #cf_span[i] 个顶点相邻的顶点数。\n\n_度集_ 是将度序列中所有不同值按升序排列得到的序列。\n\n保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。\n\n请输出构造出的图。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 度集的大小。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn] (#cf_span[1 ≤ di ≤ 1000], #cf_span[d1 < d2 < ... < dn]) —— 度集。\n\n第一行输出一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 构造出的图的边数。保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[vi] 和 #cf_span[ui] (#cf_span[1 ≤ vi, ui ≤ dn + 1]) —— 第 #cf_span[i] 条边的描述。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 度集的大小。第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn] (#cf_span[1 ≤ di ≤ 1000], #cf_span[d1 < d2 < ... < dn]) —— 度集。"},{"iden":"output","content":"第一行输出一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 构造出的图的边数。保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[vi] 和 #cf_span[ui] (#cf_span[1 ≤ vi, ui ≤ dn + 1]) —— 第 #cf_span[i] 条边的描述。"},{"iden":"examples","content":"输入\n3\n2 3 4\n输出\n8\n3 1\n4 2\n4 5\n2 5\n5 1\n3 2\n2 1\n5 3\n\n输入\n3\n1 2 3\n输出\n4\n1 2\n1 3\n1 4\n2 3"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the degree set.  \nLet $ D = (d_1, d_2, \\dots, d_n) $ be a strictly increasing sequence of positive integers, $ d_1 < d_2 < \\dots < d_n $, representing the degree set.  \nLet $ V = \\{1, 2, \\dots, d_n + 1\\} $ be the vertex set of the undirected graph.  \nLet $ \\mathbf{a} = (a_1, a_2, \\dots, a_{d_n+1}) \\in \\mathbb{Z}^{d_n+1} $ be the degree sequence of the graph, where $ a_i $ is the degree of vertex $ i $.  \nLet $ \\text{Set}(\\mathbf{a}) = \\{ a_i \\mid i \\in V \\} $ be the multiset of degrees, and its sorted distinct values equal $ D $:  \n$$\n\\text{sorted}(\\text{distinct}(\\mathbf{a})) = D\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 300 $  \n2. $ 1 \\leq d_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ d_1 < d_2 < \\dots < d_n $  \n4. The graph has no more than $ 10^6 $ edges.  \n5. The degree sequence $ \\mathbf{a} $ must contain **exactly** the distinct degrees $ d_1, d_2, \\dots, d_n $, and no others.  \n\n**Objective**  \nConstruct an undirected graph $ G = (V, E) $ with vertex set $ V = \\{1, 2, \\dots, d_n + 1\\} $ and edge set $ E \\subseteq \\binom{V}{2} $, such that:  \n- The set of degrees of vertices in $ G $ is exactly $ D $.  \n- Output the number of edges $ m = |E| $, followed by the $ m $ edges (as unordered pairs $ \\{u, v\\} $).  \n\n**Note**: The existence of such a graph is guaranteed.","simple_statement":null,"has_page_source":false}