{"raw_statement":[{"iden":"statement","content":"You are given a tree _T_ consisting of _n_ vertices. A number is written on each vertex; the number written on vertex _i_ is _a__i_. Let's denote the function _I_(_x_, _y_) as the difference between maximum and minimum value of _a__i_ on a simple path connecting vertices _x_ and _y_.\n\nYour task is to calculate ."},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 106) — the number of vertices in the tree.\n\nThe second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the numbers written on the vertices.\n\nThen _n_ - 1 lines follow. Each line contains two integers _x_ and _y_ denoting an edge connecting vertex _x_ and vertex _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_). It is guaranteed that these edges denote a tree."},{"iden":"output","content":"Print one number equal to ."},{"iden":"example","content":"Input\n\n4\n2 2 3 1\n1 2\n1 3\n1 4\n\nOutput\n\n6"}],"translated_statement":[{"iden":"statement","content":"给定一棵包含 $n$ 个顶点的树 $T$。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。定义函数 $I(x, y)$ 为连接顶点 $x$ 和 $y$ 的简单路径上所有 $a_i$ 的最大值与最小值之差。\n\n你的任务是计算 。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 树的顶点数。\n\n第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 10^6$) —— 写在顶点上的数字。\n\n接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和顶点 $y$ 的边 ($1 ≤ x, y ≤ n$, $x ≠ y$)。保证这些边构成一棵树。\n\n请输出一个等于 的数。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 树的顶点数。第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 10^6$) —— 写在顶点上的数字。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和顶点 $y$ 的边 ($1 ≤ x, y ≤ n$, $x ≠ y$)。保证这些边构成一棵树。"},{"iden":"output","content":"请输出一个等于 的数。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a_i \\in \\mathbb{Z} $ be the value assigned to vertex $ i \\in V $.\n\nDefine the function $ I(x, y) = \\max_{v \\in P_{x,y}} a_v - \\min_{v \\in P_{x,y}} a_v $, where $ P_{x,y} $ is the unique simple path between vertices $ x $ and $ y $ in $ T $.\n\nCompute:\n$$\n\\sum_{1 \\leq x < y \\leq n} I(x, y)\n$$","simple_statement":null,"has_page_source":false}