{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK128/mandarin/DELSORT.pdf), [Russian](https://www.codechef.com/download/translated/COOK128/russian/DELSORT.pdf), and [Bengali](https://www.codechef.com/download/translated/COOK128/bengali/DELSORT.pdf) as well.\r\n\r\nYou are given an array $A$ of length $N$. \r\n\r\nLet $F(L,R)$ be the array you get from $A$ after removing all occurrences of $A_L, A_{L+1}, \\dots , A_R$. In other words, for each value in $A$ between the indices $L$ and $R$, you delete every occurrence of that value, including occurrences outside the range $[L, R]$.\r\n\r\nA pair $(L,R)$ is called good if $1\\le L\\le R\\le N$ and $F(L, R)$ is sorted in non-decreasing order. In the case that $F(L, R)$ is the empty array, we say it is sorted.\r\n\r\nCount the number of good pairs.\r\n\r\n**Example:** Suppose $A\u003d[1,2,3,5,7,6,8,6,5,8]$. Then $F(4,6)$ is the array we get after deleting all occurrences of the numbers $5,7,6$. Thus, $F(4,6)\u003d[1,2,3,8,8]$. This array is sorted in non-decreasing order, so the pair $(4, 6)$ is good.\r\n\r\n### Input:\r\n- The first line of the input contains an integer $T$, denoting the number of test cases.\r\n- The first line of each test case contains an integer $N$, denoting the size of the array.\r\n- The second line of each test case contains $N$ space-separated integers, denoting the array $A$.\r\n\r\n\r\n### Output:\r\nFor each test case, output the number of good subarrays in $A$, in a separate line.\r\n\r\n### Constraints \r\n\r\n- $1 \\le T \\le 10^4$\r\n- $1 \\le N \\le 2 \\times 10^5$\r\n- $1 \\le A_i \\le 10^9$\r\n- Sum of $N$ over all test cases doesn\u0027t exceed $2 \\times 10^5$."}},{"title":"Sample 1","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\u003e3\r\n3\r\n9 8 7\r\n5\r\n5 3 1 5 2\r\n7\r\n1 5 2 5 3 5 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n7\r\n24\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n- In the **first test case** , the good subarrays are: $(1,2), (1,3), (2,3)$.\r\n\r\n - $(1,2)$ is a good subarray because the remaining array $[7]$ is sorted (we removed $9,8$). \r\n \r\n - $(1,3)$ is a good subarray because the remaining array $[]$ is sorted (we removed $9,8,7$)\r\n \r\n - $(2,3)$ is a good subarray because the remaining array $[9]$ is sorted (we removed $8,7$).\r\n\r\n- In the **second test case**, the good subarrays are $(1,2), (1,3), (1,4), (1,5), (2,4), (2,5), (3,5)$.\r\n\r\n- In the **third test case**, there are 24 possible good subarrays.\r\n - Note that $(2,2)$ is a good subarray because the remaining array $[1 , 2 , 3 , 6]$ is sorted (we removed $5 , 5$)."}}]}