Tổng cực tiểu các đoạn con

Buổi 67-68 — Mock IOI Data-structures
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved