{"trustable":true,"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":"HTML","content":"\u003cp\u003eYou are given a sequence $$$\\textbf{a}$$$ denoted by $$$(a_1, a_2, \\cdots, a_n)$$$. A query with $$$1 \\leq l \\leq r \\leq n$$$ is defined as $$$$$$Q_{max}(l, r) \u003d \\max\\{a_l, a_{l + 1}, \\cdots, a_r\\}.$$$$$$ An easy problem may ask you to calculate the sum of answers for all queries with integers $$$1 \\leq l \\leq r \\leq n$$$, but we would like to show you a harder one.\u003c/p\u003e\u003cp\u003eDefine a classifier as a container that stores unique elements. Each element in the classifier has two values, named the key value and the mapped value. The \u003cspan class\u003d\"tex-font-style-bf\"\u003ekey value\u003c/span\u003e of each element is a consecutive subsequence of $$$\\textbf{a}$$$ and the \u003cspan class\u003d\"tex-font-style-bf\"\u003emapped value\u003c/span\u003e of that element is an integer indicating the maximum value in the subsequence. The classifier only stores elements with distinct key values, which means extra duplicated elements (with the same key value) would be removed from the classifier.\u003c/p\u003e\u003cp\u003eDenote $$$S(l, r)$$$ as $$$(a_l, a_{l + 1}, \\cdots, a_r)$$$, a consecutive subsequence of $$$\\textbf{a}$$$ meeting the condition that $$$l$$$ and $$$r$$$ are integers with $$$1 \\leq l \\leq r \\leq n$$$. Now we intend to use a classifier $$$\\textbf{CA}$$$ to store all the consecutive subsequences $$$S(l, r)$$$ of $$$\\textbf{a}$$$ with their $$$Q_{max}(l, r)$$$. You are asked to determine the \u003cspan class\u003d\"tex-font-style-bf\"\u003esum of mapped values\u003c/span\u003e in $$$\\textbf{CA}$$$.\u003c/p\u003e\u003cp\u003eActually, what we defined above is a map of the form \u003cspan class\u003d\"tex-font-style-tt\"\u003emap\u0026lt;vector\u0026lt;int\u0026gt;, int\u0026gt;\u003c/span\u003e in C++ or \u003cspan class\u003d\"tex-font-style-tt\"\u003eMap\u0026lt;ArrayList\u0026lt;Integer\u0026gt;, Integer\u0026gt;\u003c/span\u003e in Java, so if you are seasoned using these data structures, you may realize that what we intend to do is to insert all possible elements $$$(S(l, r), Q_{max}(l, r))$$$ with integers $$$1 \\leq l \\leq r \\leq n$$$ into the classifier $$$\\textbf{CA}$$$ and then ask you to calculate the sum of mapped values in it.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains an integer $$$n$$$ indicating the number length of the given sequence $$$\\textbf{a}$$$, where $$$1 \\leq n \\leq 2 \\times 10^5$$$.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ positive integers $$$a_1, a_2, \\cdots, a_n$$$ describing the sequence $$$\\textbf{a}$$$, where $$$1 \\leq a_i \\leq 10^6$$$.\u003c/p\u003e\u003cp\u003eWe guarantee that there are at most $$$10$$$ test cases with $$$n \u0026gt; 1000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing the sum of mapped values in $$$\\textbf{CA}$$$.\u003c/p\u003e"}},{"title":"Examples","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\u003e2\n3\n1 2 3\n3\n2 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n14\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample case, the sum of mapped values in $$$\\textbf{CA}$$$ is equal to $$$1 + 2 + 3 + 2 + 3 + 3$$$.\u003c/p\u003e\u003cp\u003eIn the second sample case, the sum of mapped values in $$$\\textbf{CA}$$$ is equal to $$$2 + 3 + 3 + 3 + 3$$$.\u003c/p\u003e"}}]}