Problem Statement

Peak Subarrays Alice defines an array as a peak array if there exists an index i (with 0 <= i < n ) such that arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-2] > arr[n-1] In words, the array is strictly increasing up to some peak position i and then strictly decreasing afterwards. Either of the two parts may be empty, so a strictly increasing array (peak at the last element) and a strictly decreasing array (peak at the first element) both qualify. An array of size 1 is always a peak array. Alice has given you an array. You must find how many contiguous subarrays of this array are peak arrays. A subarray is a contiguous block arr[l], arr[l+1], ..., arr[r] (with l <= r ). Two subarrays are considered different if their (l, r) boundaries differ, even if their contents are equal. Input Format The first line contains an integer n , the size of the array. The second line contains n space-separated integers, the elements of the array. Outpu