{"problem":{"name":"C. 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":"CF789C"},"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":"**Definitions**\n\n*   Let $n \\in \\mathbb{Z}$ such that $2 \\le n \\le 10^5$.\n*   Let $A = (a_1, a_2, \\dots, a_n)$ be a sequence of integers, where $a_i \\in \\mathbb{Z}$ and $-10^9 \\le a_i \\le 10^9$ for all $1 \\le i \\le n$.\n*   Let $S$ be the set of valid index pairs defined as:\n    $$S = \\{ (l, r) \\in \\mathbb{Z}^2 \\mid 1 \\le l < r \\le n \\}$$\n\n**Function Definition**\n\nDefine the function $f: S \\to \\mathbb{Z}_{\\ge 0}$ as:\n$$f(l, r) = |a_l - a_r|$$\n\n*(Note: Deduced from the context of interval endpoints and absolute value constraints).*\n\n**Objective**\n\nCalculate the maximum value of $f$ over the domain $S$:\n$$ \\text{Maximize } f(l, r) \\quad \\text{subject to} \\quad (l, r) \\in S $$\n\nWhich is equivalent to finding:\n$$ \\max_{1 \\le l < r \\le n} |a_l - a_r| $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF789C","tags":["data structures","dp","two pointers"],"sample_group":[["5\n1 4 2 3 1","3"],["4\n1 5 4 7","6"]],"created_at":"2026-03-03 11:00:39"}}