{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":" Mumu likes the map in the data structure, he defines map\u003cvector\u003cint\u003e, int\u003e mp.\n mp-\u003efirst represents a set of sequences [al,...,ar].\n mp-\u003esecond represents the maximum value of this sequence.\n Now use mp(l,r) to represent the above relationship, and given a set of length n sequences [a1,...,an],\n Mumu wants to know the sum of all mp(l,r) for any l,r (1≤l≤r≤n)."}},{"title":"Input","value":{"format":"MD","content":" The input contains several test cases, and the first line contains a positive integer T indicating the number of test cases which is up to 1000.\n\n For each test case, the first line contains an integer n indicating the number length of the given sequence a, where 1≤n≤2×1e5.\n\n The second line contains n positive integers a1,a2,⋯,an describing the sequence a, where 1≤ai≤1e6.\n\n We guarantee that there are at most 10 test cases with n\u003e1000."}},{"title":"Output","value":{"format":"MD","content":" For each test case, output a line containing the sum of mp(l,r)."}},{"title":"Example","value":{"format":"MD","content":"### Sample input\n 2\n 3\n 1 2 3\n 3\n 2 3 3\n### Sample output\n 14\n 14"}},{"title":"Note","value":{"format":"MD","content":" In the first sample case, the sum of mapped values is equal to 1+2+3+2+3+3.\n\n In the second sample case, the sum of mapped values is equal to 2+3+3+3+3."}}]}