Product - MarisaOJ: Marisa Online Judge

Product

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $A$ of $n$ integers. Let's denote function $f(l, r)$ as: $$max(A_{l...r}) \times min(A_{l...r})$$ Calculate: $$ \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $$ ### Input - The first line contains an integer $n$. - The second line contains $n$ integers $A_i$. ### Output - Print the result, modulo $10^9+7$. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 4 1 4 3 1 ``` Output: ``` 58 ```