---
{"category_name":"easy","problem_code":"RARRAY","problem_name":"Range Array","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^3$\n- $1 \\leq N \\leq 10^5$\n- $1 \\leq A_i \\leq N$\n- $A_1, A_2,\\dots, A_N$ is a permutation.\n- Sum of $N$ over all test cases does not exceed $5 \\cdot 10^5$.","constraintsState":true,"subtasks":"**Subtask 1 (5 points):**\n- $1 \\leq T \\leq 20$\n- $1 \\leq N \\leq 100$\n- Sum of $N$ over all test cases does not exceed $200$.\n\n**Subtask 2 (20 points):**\n- $1 \\leq T \\leq 20$\n- $1 \\leq N \\leq 2500$\n- Sum of $N$ over all test cases does not exceed $2500$.\n\n**Subtask 3 (75 points):**\n- Original constraints","subtasksState":true,"inputFormat":"- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains a single integer $N$.\n- The second line contains $N$ space-separated integer $A_1, A_2,\\dots, A_N$. ","inputFormatState":true,"outputFormat":"For each test case, print a single line containing one integer - the number of good pairs.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n2\n2 1\n3 \n1 2 3\n4\n1 3 2 4\n","output":"2\n6\n6\n","explanation":"**Test case $1$**: The range arrays are $A_{1, 1} = [\\;], A_{2, 2} = [\\;], A_{1, 2} = [2, 1]$. The first two of them are empty lists and hence sorted.\n\n**Test case $2$**: Elements in all the six range arrays are sorted in increasing order.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"soumyadeep_21","problem_tester":"","date_added":"7-07-2021","tags":{"0":"easy","1":"ltime100","2":"soumyadeep_21","3":"two"},"problem_difficulty_level":"Unavailable","best_tag":"Two Pointers","editorial_url":"https://discuss.codechef.com/problems/RARRAY","time":{"view_start_date":1632585602,"submit_start_date":1632585602,"visible_start_date":1632585602,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=RARRAY","is_proctored":false,"visitedContests":{},"layout":"problem"}
---
### Read problem statements in [Mandarin](https://www.codechef.com/download/translated/LTIME100/mandarin/RARRAY.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME100/bengali/RARRAY.pdf), [Russian](https://www.codechef.com/download/translated/LTIME100/russian/RARRAY.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME100/vietnamese/RARRAY.pdf) as well.
Chef has an array $A$ of length $N$. Chef constructs the range-array $A_{L,R}$ as follows:
- First, Chef considers the subarray $A_L, A_{L + 1}, . . . , A_{R}$.
- Then Chef removes the integers that do not belong to the range $[L, R]$ from the subarray to finally create the range-array $A_{L, R}$.
For example, consider the array $A = [1, 3, 2, 4]$, then the range-arrays are: $A_{1, 1} = [1], A_{1, 2} = [1], A_{1, 3} = [1, 3, 2], A_{1, 4} = [1, 3, 2, 4],$ $A_{2, 2} = [\;]$, $A_{2, 3} = [3, 2],$ $A_{2, 4} = [3, 2, 4]$ and so on.
Chef is given a permutation $A_1, A_2,\dots, A_N$ of length $N$. A pair of integers $(L, R) \;(1 \leq L \leq R \leq N)$ is called good if all the elements in the range array $A_{L, R}$ are sorted in increasing order. In case, a range array is an empty list, it is considered to be sorted. Chef tries to find the number of good pairs $(L, R)$, but fails. Can you help him?
<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>