{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"小 x 喜欢吃巧克力,但是他有一个癖好,他在吃巧克力的时候喜欢从甜度小的开始吃,并且在之后每次吃的巧克力必须比前一个巧克力甜。\n小 x 有 $n$ 个巧克力,从左到右甜度分别为 $a_1, a_2, ... , a_n$, 现在他要从左到右按顺序开始吃,只有当满足 $a_1 \u003c a_2 \u003c ... \u003c a_n$ 的时候,小 x 才可以吃到巧克力。 但是巧克力可能不符合他吃的条件,因此需要 **做出改变** 。\n\n为了 **做出改变**, 小 x 去了魔法峡谷学习魔法,现在它可以对所有的巧克力的 **甜度** 做出改变,假设改变后的巧克力甜度分别为 $b_1, b_2, ... , b_n$, 那么小 x 需要花费 $max( |a_i - b_i |) (\\forall i \\in [1, n] ) $ (即所有的巧克力变化前后的 **最大** 差异) 个能量石。\n\n现在请你告诉小 x ,他如果想吃到所有的巧克力需要花费的能量石最少是多少?"}},{"title":"Input","value":{"format":"MD","content":"第一行有一个整数 $T (1 \\le T \\le 10 )$,表示 $T$ 组数据。\n\n对于每组数据: \n\n第一行包含一个整数 $n ( 1 \\le n \\le 10^5) $,表示巧克力的个数。\n第二行包含 $n$ 个 正整数 $a_1, a_2 , ... , a_n (1 \\le a_i \\le 10^6 , \\forall i \\in [1,n] )$ 表示从左到右巧克力的甜度。\n\nTips: 巧克力的甜度在施法之后可以为负数,但是必须为整数。\n\n"}},{"title":"Output","value":{"format":"MD","content":"对于每一个测试样例,输出两行:\n\n第一行输出:`Case #t:` , $t$ 代表第 $t$ 组测试数据。\n\n\n第二行输出一个正整数,代表小 x 可以吃到所有的巧克力需要花费的最少能量石。"}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e3\n2\n3 4\n2\n3 3\n3\n1 4 3\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003eCase #1:\n0\nCase #2:\n1\nCase #3:\n1\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}