Tổng cực tiểu các đoạn con
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy số nguyên dương $A_1, A_2, \dots, A_N$. Hãy tính tổng biên độ của tất cả các đoạn con liên tiếp: \[\sum_{1 \le l \le r \le N} \left( \max_{l \le i \le r} A_i - \min_{l \le i \le r} A_i \right)\] In ra kết quả chia lấy dư cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 5 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
Kết quả
In ra một số nguyên duy nhất là kết quả bài toán modulo $10^9 + 7$.
Subtasks
- Subtask 1 (20%): $N \le 500$.
- Subtask 2 (30%): $N \le 5000$.
- Subtask 3 (50%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 1 4 2 3 |
14 |
Community Discussion