{"raw_statement":[{"iden":"statement","content":"You are given an array _a_ consisting of _n_ elements. The _imbalance value_ of some subsegment of this array is the difference between the maximum and minimum element from this segment. The _imbalance value_ of the array is the sum of _imbalance values_ of all subsegments of this array.\n\nFor example, the _imbalance value_ of array \\[1, 4, 1\\] is 9, because there are 6 different subsegments of this array:\n\n*   \\[1\\] (from index 1 to index 1), _imbalance value_ is 0;\n*   \\[1, 4\\] (from index 1 to index 2), _imbalance value_ is 3;\n*   \\[1, 4, 1\\] (from index 1 to index 3), _imbalance value_ is 3;\n*   \\[4\\] (from index 2 to index 2), _imbalance value_ is 0;\n*   \\[4, 1\\] (from index 2 to index 3), _imbalance value_ is 3;\n*   \\[1\\] (from index 3 to index 3), _imbalance value_ is 0;\n\nYou have to determine the _imbalance value_ of the array _a_."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 106) — size of the array _a_.\n\nThe second line contains _n_ integers _a_1, _a_2... _a__n_ (1 ≤ _a__i_ ≤ 106) — elements of the array."},{"iden":"output","content":"Print one integer — the _imbalance value_ of _a_."},{"iden":"example","content":"Input\n\n3\n1 4 1\n\nOutput\n\n9"}],"translated_statement":[{"iden":"statement","content":"你被给定一个包含 $n$ 个元素的数组 $[a]$。该数组某个子段的 _不平衡值_ 定义为该子段中最大元素与最小元素的差。数组的 _不平衡值_ 是该数组所有子段的 _不平衡值_ 之和。\n\n例如，数组 $[1, 4, 1]$ 的 _不平衡值_ 为 $9$，因为该数组有 $6$ 个不同的子段：\n\n你需要确定数组 $[a]$ 的 _不平衡值_。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 数组 $[a]$ 的大小。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 ≤ a_i ≤ 10^6$) —— 数组的元素。\n\n请输出一个整数 —— 数组 $[a]$ 的 _不平衡值_。"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 数组 $[a]$ 的大小。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 ≤ a_i ≤ 10^6$) —— 数组的元素。"},{"iden":"output","content":"请输出一个整数 —— 数组 $[a]$ 的 _不平衡值_。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\mathbb{Z}^+ $.\n\nLet $ \\mathcal{S} = \\{ [i,j] \\mid 1 \\leq i \\leq j \\leq n \\} $ be the set of all contiguous subsegments (subarrays) of $ A $.\n\nFor a subsegment $ [i,j] $, define its imbalance value as:  \n$$\n\\text{imbalance}([i,j]) = \\max_{k \\in [i,j]} a_k - \\min_{k \\in [i,j]} a_k\n$$\n\n**Objective**  \nCompute the total imbalance value of the array:  \n$$\n\\sum_{[i,j] \\in \\mathcal{S}} \\left( \\max_{k=i}^j a_k - \\min_{k=i}^j a_k \\right)\n$$","simple_statement":null,"has_page_source":false}