Sum of Subarray

Problem Statement

Sum of Subarray Problem Description You are given an array A of length N , indexed from 1. For any subarray of A , a subsequence of that subarray is obtained by erasing some (possibly zero) elements of the subarray. The erased elements need not be consecutive. A subsequence of length K (where K >= 3 ) is good if every index i of the subsequence with 1 < i < K satisfies |A_i - A_(i-1)| + |A_(i+1) - A_i| = |A_(i-1) - A_(i+1)| Here A_i denotes the i -th element of the subsequence itself. The value of a subarray S is the maximum length of a good subsequence of S . If S has no good subsequence - in particular whenever S has fewer than three elements - the value of S is 0 . Find the sum of the values of all N * (N + 1) / 2 subarrays of A . Input Format The first line contains a single integer N , the length of the array. The second line contains N space-separated integers A_1, A_2, ..., A_N . Output Format Print a single integer: the sum of the values of all subarrays of A . Constra