1. You are given an array(arr) of integers. 2. You have to find the alternating subsequence wit maximum sum. 3. The alternating subsequence should start with the first element of the array. 4. The first step in alternating subsequence should be decreasing, then increasing, then decreasing and so on. Note -> If the array contains only one element, then your answer should be that element itself.
Input Format
A number N arr1 arr2... N integers
Output Format
Check the sample output and question video.
Constraints
1 <= N <= 10^4 1 <= arr[i] <= 10^4
Example
Input
6 5 3 2 5 2 1
Output
15