{"problem":{"name":"A. Functions again","description":{"content":"Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arr","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF788A"},"statements":[{"statement_type":"Markdown","content":"Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function _f_, which is defined as follows:\n\nIn the above formula, 1 ≤ _l_ < _r_ ≤ _n_ must hold, where _n_ is the size of the Main Uzhlyandian Array _a_, and |_x_| means absolute value of _x_. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of _f_ among all possible values of _l_ and _r_ for the given array _a_.\n\n## Input\n\nThe first line contains single integer _n_ (2 ≤ _n_ ≤ 105) — the size of the array _a_.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (-109 ≤ _a__i_ ≤ 109) — the array elements.\n\n## Output\n\nPrint the only integer — the maximum value of _f_.\n\n[samples]\n\n## Note\n\nIn the first sample case, the optimal value of _f_ is reached on intervals \\[1, 2\\] and \\[2, 5\\].\n\nIn the second case maximal value of _f_ is reachable only on the whole array.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"乌日兰迪亚又发生了什么事……街头爆发了骚乱……著名的乌日兰迪亚超级英雄羊神谢恩和长颈鹿神斯塔斯被召来挽救局势。到达后，他们发现市民们正担忧主乌日兰迪亚函数 #cf_span[f] 的最大值，该函数定义如下：\n\n在上述公式中，必须满足 #cf_span[1 ≤ l < r ≤ n]，其中 #cf_span[n] 是主乌日兰迪亚数组 #cf_span[a] 的大小，而 #cf_span[|x|] 表示 #cf_span[x] 的绝对值。但这些英雄在学校逃掉了数学课，因此他们向你求助。请帮助他们计算在给定数组 #cf_span[a] 的所有可能的 #cf_span[l] 和 #cf_span[r] 取值下，#cf_span[f] 的最大值。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 数组 #cf_span[a] 的大小。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (-#cf_span[109 ≤ ai ≤ 109]) —— 数组元素。\n\n请输出一个整数 —— #cf_span[f] 的最大值。\n\n在第一个样例中，#cf_span[f] 的最优值在区间 #cf_span[[1, 2]] 和 #cf_span[[2, 5]] 上取得。\n\n在第二个样例中，#cf_span[f] 的最大值仅在完整数组上可达。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 数组 #cf_span[a] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (-#cf_span[109 ≤ ai ≤ 109]) —— 数组元素。\n\n## Output\n\n请输出一个整数 —— #cf_span[f] 的最大值。\n\n[samples]\n\n## Note\n\n在第一个样例中，#cf_span[f] 的最优值在区间 #cf_span[[1, 2]] 和 #cf_span[[2, 5]] 上取得。在第二个样例中，#cf_span[f] 的最大值仅在完整数组上可达。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of $ n $ integers, where $ 2 \\leq n \\leq 10^5 $ and $ -10^9 \\leq a_i \\leq 10^9 $.\n\nDefine the function $ f(l, r) $ for $ 1 \\leq l < r \\leq n $ as:\n\n$$\nf(l, r) = \\left| \\sum_{i=l+1}^{r-1} a_i \\right|\n$$\n\nThat is, $ f(l, r) $ is the absolute value of the sum of elements strictly between indices $ l $ and $ r $ (excluding $ a_l $ and $ a_r $).\n\n**Objective:** \nFind the maximum value of $ f(l, r) $ over all valid pairs $ (l, r) $ with $ 1 \\leq l < r \\leq n $.\n\n---\n\n**Equivalent Reformulation:** \nLet $ S(i, j) = \\sum_{k=i}^{j} a_k $ denote the sum of subarray from index $ i $ to $ j $ (inclusive). \nThen:\n\n$$\nf(l, r) = \\left| S(l+1, r-1) \\right|\n$$\n\nWe seek:\n\n$$\n\\max_{1 \\leq l < r \\leq n} \\left| S(l+1, r-1) \\right|\n$$\n\nNote: When $ r = l+1 $, the inner sum is over an empty range, so $ f(l, l+1) = 0 $.\n\nThus, the problem reduces to: \n**Find the maximum absolute value of the sum of any contiguous subarray of length at least 1 (i.e., excluding single-element subarrays from being considered as inner sums), but note that the inner sum $ S(l+1, r-1) $ can be of length 0 (yielding 0) or more.**\n\nBut since we are taking absolute value and seeking maximum, we can rephrase:\n\nLet $ b $ be the array of all contiguous subarray sums of $ a $, excluding those of length 0 and those that correspond to $ l+1 > r-1 $ (i.e., inner sums of length ≥ 1). Then we want $ \\max |s| $ over all such $ s \\in b $.\n\nAlternatively, since $ S(l+1, r-1) = S(1, r-1) - S(1, l) $, we can define prefix sums:\n\nLet $ p_0 = 0 $, and $ p_i = \\sum_{k=1}^{i} a_k $ for $ 1 \\leq i \\leq n $.\n\nThen:\n\n$$\nS(l+1, r-1) = p_{r-1} - p_l\n$$\n\nSo:\n\n$$\nf(l, r) = |p_{r-1} - p_l|, \\quad \\text{for } 0 \\leq l < r-1 \\leq n-1\n$$\n\nLet $ i = l $, $ j = r-1 $. Then the constraint $ 1 \\leq l < r \\leq n $ becomes:\n\n- $ l \\in [0, n-2] $ (since $ l = 0 $ corresponds to $ a_1 $ being excluded, $ l = n-2 $ means $ r = n $)\n- $ j \\in [1, n-1] $\n- and $ i < j $\n\nSo we are to compute:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} |p_j - p_i|\n$$\n\nThis is the well-known problem: **Maximum absolute difference between two prefix sums with $ i < j $**.\n\nWhich is equivalent to:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} (p_j - p_i) \\quad \\text{and} \\quad \\max_{0 \\leq i < j \\leq n-1} (p_i - p_j)\n$$\n\nSo:\n\n$$\n\\max \\left( \\max_{j} p_j - \\min_{i < j} p_i, \\max_{i} p_i - \\min_{j > i} p_j \\right)\n$$\n\nBut since we are taking absolute value, it's simply:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} |p_j - p_i| = \\max(p_{\\max} - p_{\\min})\n$$\n\nwhere $ p_{\\max} = \\max_{0 \\leq k \\leq n-1} p_k $, $ p_{\\min} = \\min_{0 \\leq k \\leq n-1} p_k $, and we require that the maximum occurs for some $ i < j $, which is guaranteed if we consider the global min and max over the entire prefix array (as long as the min occurs before the max, or vice versa — but if not, we can still compute the maximum difference over all pairs).\n\nActually, the maximum absolute difference between any two prefix sums $ p_i, p_j $ with $ i < j $ is equal to:\n\n$$\n\\max\\left( \\max_{0 \\leq j \\leq n-1} p_j - \\min_{0 \\leq i < j} p_i, \\max_{0 \\leq i \\leq n-1} p_i - \\min_{i < j \\leq n-1} p_j \\right)\n$$\n\nBut a simpler and correct approach is:\n\n> The maximum value of $ |p_j - p_i| $ for $ 0 \\leq i < j \\leq n-1 $ is equal to $ \\max p_k - \\min p_k $ over $ k \\in [0, n-1] $, **provided** that the global maximum occurs after the global minimum. If not, we need to ensure $ i < j $.\n\nBut note: we are allowed to choose any $ i < j $. So the maximum difference $ p_j - p_i $ over $ i < j $ is:\n\n$$\n\\max_{j} \\left( p_j - \\min_{i < j} p_i \\right)\n$$\n\nSimilarly, the maximum of $ p_i - p_j $ for $ i < j $ is:\n\n$$\n\\max_{i} \\left( p_i - \\min_{j > i} p_j \\right)\n$$\n\nBut since we take absolute value, we can compute:\n\n$$\n\\max \\left( \\max_{0 \\leq i < j \\leq n-1} (p_j - p_i), \\max_{0 \\leq i < j \\leq n-1} (p_i - p_j) \\right)\n= \\max_{0 \\leq i, j \\leq n-1, i \\ne j} |p_i - p_j|\n$$\n\nAnd since the maximum absolute difference between any two elements in a set is $ \\max - \\min $, we can compute:\n\nLet $ P = \\{ p_0, p_1, \\dots, p_{n-1} \\} $\n\nThen:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} |p_j - p_i| = \\max(P) - \\min(P)\n$$\n\n**Why?** Because if the global maximum occurs at index $ j $ and global minimum at index $ i $, and if $ i < j $, then we are done. If $ i > j $, then we can still find some pair $ i' < j' $ such that $ p_{j'} - p_{i'} = \\max(P) - \\min(P) $, because the maximum difference in absolute value over all unordered pairs is always $ \\max - \\min $, and since we are allowed to pick any $ i < j $, as long as $ \\max $ and $ \\min $ are in the prefix array, and we can always find a pair where the larger one comes after the smaller one (or vice versa for negative), but the absolute value makes it symmetric.\n\nActually, **this is not always true** if the global min occurs after the global max. For example: $ p = [10, 1, 5] $, then $ \\max = 10 $, $ \\min = 1 $, but $ \\max - \\min = 9 $, but if the max is at index 0 and min at index 1, then we cannot use $ p_0 - p_1 $ as $ i < j $, but we can use $ p_2 - p_1 = 4 $, or $ p_0 - p_1 = 9 $, but $ i=0, j=1 $, and $ i < j $, so we **can** use it.\n\nWait — $ i $ and $ j $ are indices in the prefix array, and we require $ i < j $, meaning the index of the first prefix sum is less than the index of the second.\n\nSo if $ p_i = \\min $ at index $ i $, $ p_j = \\max $ at index $ j $, and $ i < j $, then $ p_j - p_i = \\max - \\min $ is valid.\n\nIf $ i > j $, then $ p_i - p_j = \\max - \\min $, but $ i > j $, so we cannot use that pair because we require $ i < j $ in the pair $ (i, j) $ for $ p_j - p_i $.\n\nWait — in our expression $ f(l, r) = |p_{r-1} - p_l| $, and we have $ l < r-1 $, so $ i = l $, $ j = r-1 $, and $ i < j $. So we require the index of the first prefix to be less than the index of the second.\n\nTherefore, the maximum value of $ p_j - p_i $ for $ i < j $ is:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} (p_j - p_i)\n$$\n\nAnd the maximum value of $ p_i - p_j $ for $ i < j $ is:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} (p_i - p_j) = - \\min_{0 \\leq i < j \\leq n-1} (p_j - p_i)\n$$\n\nBut we take absolute value, so:\n\n$$\n\\max_{0 \\leq i < j \\leq n-1} |p_j - p_i| = \\max\\left( \\max_{i p_j $, we can compute both.\n\nBut there is a standard result: \n> The maximum absolute difference between any two elements in a sequence, with the constraint that the first element comes before the second, is equal to the maximum difference between any two prefix sums where the later one is subtracted by the earlier one, and we take the maximum over all such pairs.\n\nActually, the maximum value of $ |p_j - p_i| $ for $ i < j $ is equal to:\n\n$$\n\\max\\left( \\max_{0 \\leq j \\leq n-1} p_j - \\min_{0 \\leq i < j} p_i, \\max_{0 \\leq i \\leq n-1} p_i - \\min_{i < j \\leq n-1} p_j \\right)\n$$\n\nBut a simpler and correct method is:\n\nLet $ m = \\min_{0 \\leq k \\leq n-1} p_k $, $ M = \\max_{0 \\leq k \\leq n-1} p_k $\n\nThen the maximum absolute difference over all $ i < j $ is not necessarily $ M - m $, because if $ m $ occurs after $ M $, then $ M - m $ cannot be achieved with $ i < j $.\n\nBut we can compute:\n\n- $ \\text{max\\_diff} = 0 $\n- $ \\text{min\\_so\\_far} = p_0 $\n- For $ j = 1 $ to $ n-1 $:\n - $ \\text{max\\_diff} = \\max(\\text{max\\_diff}, p_j - \\text{min\\_so\\_far}) $\n - $ \\text{min\\_so\\_far} = \\min(\\text{min\\_so\\_far}, p_j) $\n\nThen the maximum of $ p_j - p_i $ for $ i < j $ is this `max_diff`.\n\nSimilarly, to get the maximum of $ p_i - p_j $ for $ i < j $, we can reverse: compute maximum of $ p_i - p_j $ for $ i < j $, which is equivalent to computing $ \\max_{i p_j $, so we are covering both cases.\n\nAlternatively, since $ \\max_{i