409730: GYM103708 L The last problem

The Leones(0,0,0) have finally retired from competition after several years in college and have decided to take a nice vacation at the beach. Although they are a little sad to leave their years of competition in the Grand Prix of Mexico.

They were relaxing in an enramada, ordering some piña coladas and looking at the sea in the distance, when a group of sailboats began to line up on the horizon... it just so happened that the sailboats had numbered sails. After a few minutes the great sage of the Caribbean arrived (also known as the man who sells prepared coconuts) and proposed a riddle in which they would win free coconuts if they solved it correctly. The team could not refuse to do one last problem and they got ready to solve it.

The riddle said the following: Visualize all the sailboats on the horizon as a list of numbers $$$A$$$ then take an element $$$A_i$$$ and calculate the sum of elements for all possible ranges $$$[l, r]$$$ such that $$$A_i $$$ has the maximum value among all elements between $$$A_l$$$ and $$$A_r$$$ inclusive.

This riddle was clearly very simple, so after the team answered it correctly, the wise man from the Caribbean decided to make the riddle even more interesting. Now, for the prize of free coconuts for life, the riddle said: let's say that the previous riddle is the result of $$$ f(i)$$$ for a sailboat at position $$$i$$$, then solve the sum of $$$f(i)$$$ for all existing sailboats

This puzzle has exceeded the capabilities of the participants and now they ask for help from the next generations of ICPC

In the first line a number $$$n(1 \leq n \leq 10^6)$$$ the number of sailboats in the sea.

In the second line $$$n$$$ integers that represents the numbers in the sails of the boats. $$$(-10^9 \leq a_i \leq 10^9)$$$

The first and only line in the output is the answer to the riddle modulo $$$10^9 + 7$$$

4
1 2 5 3

58

7
1 2 3 4 6 5 1

297