{"trustable":true,"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":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e能量立方体被用作异能能量的储存。有$n$个编号为$1, 2, \\dots, n$的城市可以在其中进行交易。第$i$个城市的能量立方体交易价格为每个$a_i$美元。Noswal是一个狡猾的商人,想要静悄悄地通过购买和转售能量立方体来发财。为了避免被警察发现,Noswal将前往第$i$个城市,并在第$i$天选择以下三个选项中的一个:\u003cbr\u003e\u003cbr\u003e1. 花费$a_i$美元购买一个能量立方体\u003cbr\u003e2. 如果他至少拥有一个能量立方体,则转售一个能量立方体并获得$a_i$美元\u003cbr\u003e3. 什么都不做\u003cbr\u003e\u003cbr\u003e显然,Noswal可以同时拥有多个能量立方体。在前往第$n$个城市后,他将回家并远离警察。他想知道自己能够赚取的最大利润。与此同时,为了降低风险,他希望最小化交易次数(包括购买和出售)以获得最大利润。Noswal是一个狡猾而成功的商人,所以你可以假设他一开始就有无限的钱。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例。输入的第一行包含一个正整数$T$($T\\leq 250$),表示测试用例的数量。对于每个测试用例:\u003cbr\u003e第一行包含一个整数$n$($1\\leq n \\leq 10^5$)\u003cbr\u003e第二行包含$n$个整数$a_1, a_2, \\dots, a_n$,其中$a_i$表示第$i$个城市的能量立方体的交易价格(购买或出售)。 ($1 \\leq a_i \\leq 10^9$)\u003cbr\u003e保证所有$n$的总和不超过$5\\times 10^5$。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,打印一行,包含两个整数——最大利润和获得最大利润所需的最小交易次数。"}},{"title":"样例","value":{"format":"HTML","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\u003e3\r\n4\r\n1 2 10 9\r\n5\r\n9 5 9 10 5\r\n2\r\n2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16 4\r\n5 2\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e在第一个案例中,他将在1、2购买,并在3、4出售。 \u003ci\u003e利润 \u003d - 1 - 2 + 10 + 9 \u003d 16\u003c/i\u003e\u003cbr\u003e在第二个案例中,他将在2购买,并在4出售。 \u003ci\u003e利润 \u003d - 5 + 10 \u003d 5\u003c/i\u003e\u003cbr\u003e在第三个案例中,他将什么都不做,也不赚钱。 \u003ci\u003e利润 \u003d 0\u003c/i\u003e\u003cbr\u003e"}}]}