Count Subarrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
Given an array A_{1}, A_{2}, ..., A_{N}, count the number of subarrays of array A which are nondecreasing.
A subarray A[i, j], where 1 ≤ i ≤ j ≤ N is a sequence of integers A_{i}, A_{i+1}, ..., A_{j}.
A subarray A[i, j] is nondecreasing if A_{i} ≤ A_{i+1} ≤ A_{i+2} ≤ ... ≤ A_{j}. You have to count the total number of such subarrays.
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of array.
The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of the array.
Output
For each test case, output in a single line the required answer.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{9}
Subtasks
 Subtask 1 (20 points) : 1 ≤ N ≤ 100
 Subtask 2 (30 points) : 1 ≤ N ≤ 1000
 Subtask 3 (50 points) : Original constraints
Example
Input: 2 4 1 4 2 3 1 5 Output: 6 1
Explanation
Example case 1.
All valid subarrays are A[1, 1], A[1, 2], A[2, 2], A[3, 3], A[3, 4], A[4, 4].
Note that singleton subarrays are identically nondecreasing.
Example case 2.
Only single subarray A[1, 1] is nondecreasing.
Author:  darkshadows 
Editorial  http://discuss.codechef.com/problems/SUBINC 
Tags  darkshadows, dynamicprogramming, oct15, simple 
Date Added:  9062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 