# 最小值加权的区间和

预估时间限制：1.5 秒。内存限制：2048 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一份读数报告需要统计所有连续片段。每个片段的贡献等于它的最小读数乘以读数总和；负读数也参与计算。

(本故事由GPT-6重写)

## 形式化问题描述

给定长度为 $N$ 的整数序列 $A_1,\ldots,A_N$ ，求

$$\sum_{1\le L\le R\le N}\left(\min_{L\le i\le R}A_i\right)\left(\sum_{i=L}^{R}A_i\right).$$

每个非空连续子区间恰好贡献一次，包括长度为一的区间。输出精确整数，不取模；答案可能为负数。

## 输入格式

第一行一个整数 $N$ .第二行 $N$ 个整数 $A_1,\ldots,A_N$ .

## 输出格式

输出一行一个整数，表示上述总和。

## 样例

### 样例 1

### 输入

```text
7
3 4 2 -1 5 7 6
```

### 输出

```text
226
```

### 样例 2

### 输入

```text
5
1 1 -1 1 1
```

### 输出

```text
-1
```

### 样例 3

### 输入

```text
2
1000000000 1000000000
```

### 输出

```text
4000000000000000000
```

## 样例解释

第一组所有区间的贡献之和为 $226$ .第二组按区间长度一到五汇总的贡献分别为 $5,4,-3,-4,-3$ ，总和为 $-1$ .第三组的两个单点各贡献 $10^{18}$ ，长度二的区间贡献 $2\times10^{18}$ .

## 数据范围与保证

$1\le N\le10^7$ , $-10^9\le A_i\le10^9$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |