{"raw_statement":[{"iden":"statement","content":"You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_.\n\nCalculate the weight of the minimum spanning tree in this graph."},{"iden":"input","content":"The first line contains _n_ (1 ≤ _n_ ≤ 200000) — the number of vertices in the graph.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < 230) — the numbers assigned to the vertices."},{"iden":"output","content":"Print one number — the weight of the minimum spanning tree in the graph."},{"iden":"examples","content":"Input\n\n5\n1 2 3 4 5\n\nOutput\n\n8\n\nInput\n\n4\n1 2 3 4\n\nOutput\n\n8"}],"translated_statement":[{"iden":"statement","content":"给定一个具有 #cf_span[n] 个顶点的完全无向图。每个顶点被分配了一个数 #cf_span[ai]，且顶点 #cf_span[i] 与顶点 #cf_span[j] 之间的边的权重等于 #cf_span[ai xor aj]。\n\n计算该图的最小生成树的权重。\n\n第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。\n\n输出一个数——图中最小生成树的权重。\n\n"},{"iden":"input","content":"第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。"},{"iden":"output","content":"输出一个数——图中最小生成树的权重。"},{"iden":"examples","content":"输入51 2 3 4 5输出8输入41 2 3 4输出8"}],"sample_group":[],"show_order":[],"formal_statement":"Given a complete undirected graph with $ n $ vertices, where each vertex $ i $ is assigned a value $ a_i \\in [0, 2^{30}) $, and the weight of edge $ (i, j) $ is $ a_i \\oplus a_j $ (XOR), compute the weight of the minimum spanning tree (MST).\n\n**Formal Statement:**\n\nLet $ V = \\{1, 2, \\dots, n\\} $, and let $ a : V \\to \\mathbb{Z} $ with $ 0 \\leq a_i < 2^{30} $.  \nDefine the edge weight function $ w : V \\times V \\to \\mathbb{Z}_{\\geq 0} $ as:  \n$$\nw(i, j) = a_i \\oplus a_j \\quad \\text{for all } i \\ne j\n$$\n\nCompute the total weight of the minimum spanning tree of the complete graph $ K_n $ with edge weights $ w(i, j) $.\n\n**Objective:**  \n$$\n\\min_{T \\in \\mathcal{T}} \\sum_{(i,j) \\in E(T)} (a_i \\oplus a_j)\n$$\nwhere $ \\mathcal{T} $ is the set of all spanning trees of $ K_n $.","simple_statement":null,"has_page_source":false}