5836.找乐子2

## 题目描述

给定一个正整数序列 $a\_1, a\_2, \dots, a\_n$，求：

$$ \sum\_{i=1}^{n} \sum\_{j=i}^{n} \left( \max\_{i \le k \le j} \{a\_k\} \times \min\_{i \le k \le j} \{a\_k\} \right) $$

## 输入格式

第一行包含一个整数 $n$，表示序列的长度。

接下来 $n$ 行，每行包含一个正整数，依次表示序列中的元素 $a\_1, a\_2, \dots, a\_n$。

## 输出格式

输出一个整数，表示答案对 $10^9$ 取模后的结果。

## 输入输出样例

### 输入样例 1

```
4
2
4
1
4
```

### 输出样例 1

```
65
```

## 提示/说明

### 样例 1 解释

给定序列为 `[2, 4, 1, 4]`。所有子区间 $[i, j]$ 的最大值、最小值及其乘积如下：

| 子区间 $[i, j]$ | 子数组元素 | 最大值 $\max$ | 最小值 $\min$ | 乘积 $\max \times \min$ |
| :---: | :--- | :---: | :---: | :---: |
| $[1, 1]$ | `[2]` | $2$ | $2$ | $4$ |
| $[1, 2]$ | `[2, 4]` | $4$ | $2$ | $8$ |
| $[1, 3]$ | `[2, 4, 1]` | $4$ | $1$ | $4$ |
| $[1, 4]$ | `[2, 4, 1, 4]` | $4$ | $1$ | $4$ |
| $[2, 2]$ | `[4]` | $4$ | $4$ | $16$ |
| $[2, 3]$ | `[4, 1]` | $4$ | $1$ | $4$ |
| $[2, 4]$ | `[4, 1, 4]` | $4$ | $1$ | $4$ |
| $[3, 3]$ | `[1]` | $1$ | $1$ | $1$ |
| $[3, 4]$ | `[1, 4]` | $4$ | $1$ | $4$ |
| $[4, 4]$ | `[4]` | $4$ | $4$ | $16$ |

将所有乘积相加：$4 + 8 + 4 + 4 + 16 + 4 + 4 + 1 + 4 + 16 = 65$。
对 $10^9$ 取模后的结果为 $65$。

### 数据规模与约定

对于所有数据，保证：
- $1 \le n \le 10^5$；
- $0 \le a\_i \le 10^9$。