Beautiful Segments

All submissions for this problem are available.
You are given an array A of length N. You have to output the total number of beautiful segments in the given array . Beautiful segment is a contiguous subarray of odd length L (L >= 3) of an array, such that the sequence of numbers from first element(inclusive) to middle element(inclusive) is non decreasing and the sequence of numbers from middle element(inclusive) to last element (inclusive) is strictly decreasing.e.g. "1 2 3 3 0 1 2", "1 2 3 2 1" are beautiful segments but "1 2 3 3 5", "1 2 3 3 3" are not.
Note that beautiful segments can overlap. Also one beautiful segment can lie completely inside other one.
Input:
 First line will contain $T$, number of testcases. Testcases will follow.
 First line of each test case will contain a number N denoting number of elements in the array. Second line will contain N space seperated integers denoting the elements of the array.
Output:
Output T lines, one for each test case, denoting the total number of beautiful segments in the array of the corresponding testcase.
Constraints:
 $1 \leq T \leq 20$
 $0 \leq n \leq 500$
 $1000000 \leq A[i] \leq 1000000$
Subtasks:
 30 points : $1 \leq n \leq 100$
 70 points : Original Constraints
Sample Input:
4
4
1 2 1 4
3
1 1 1
5
1 2 1 2 1
5
1 2 3 2 1
Sample Output:
1
0
2
2
Explanation:
Testcase 1: The sequence [1 2 1] increases from 1 to 2, then decreases from 2 to 1. There is only one such sequence.
Testcase 2: There are no beautiful segments.
Testcase 3: There are two beautiful segments: [1 2 1] and [1 2 1].
Testcase 4: There are two beautiful segments: [2 3 2], [1 2 3 2 1]. (Note: Beautiful segments can be nested inside each other).
Author:  hemanthkumar9 
Tags  hemanthkumar9 
Date Added:  26122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH 3.6 
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. 