Transforming data into some other data is typical of a programming job. This problem is about a particular kind of transformation which we'll call the max transform.
Let be a zero-indexed array of integers. For , let denote the subarray of from index to index , inclusive.
Let's define the max transform of as the array obtained by the following procedure:
The returned array is defined as the max transform of . We denote it by .
Complete the function solve that takes an integer array as input.
Given an array , find the sum of the elements of , i.e., the max transform of the max transform of . Since the answer may be very large, only find it modulo .
The first line of input contains a single integer denoting the length of .
The second line contains space-separated integers denoting the elements of .
Print a single line containing a single integer denoting the answer.
Sample Input 0
3 2 1
Sample Output 0
In the sample case, we have:
Therefore, the sum of the elements of is .