Sereja và các dãy con

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho dãy số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ .

Xét tất cả các dãy con không giảm phân biệt của $a$ . Với mỗi dãy con $y = (y_{1}, y_{2}, \dots, y_{r})$ thu được, đếm số dãy số nguyên dương $x = (x_{1}, x_{2}, \dots, x_{r})$ cùng độ dài thỏa mãn $x_{1} \leq y_{1}$ , $x_{2} \leq y_{2}$ , $\dots$ , $x_{r} \leq y_{r}$ .

Hãy tính tổng số lượng dãy $x$ đếm được trên tất cả các dãy con không giảm phân biệt của $a$ . Vì kết quả có thể rất lớn, hãy in ra theo modulo $10^{9} + 7$ .

Hai dãy con được coi là phân biệt nếu chúng khác nhau khi so sánh theo giá trị (không tính vị trí xuất hiện trong $a$ ). Ví dụ, với dãy $a = (1, 2, 2)$ , hai dãy con không giảm phân biệt chứa cả hai giá trị $1$ và $2$ chỉ được tính một lần là $(1, 2)$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất là đáp án theo modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
1 42	42	Dãy con không giảm phân biệt duy nhất là $(42)$ , có $42$ dãy $x$ thỏa mãn.
3 1 2 2	13	Các dãy con không giảm phân biệt: $(1), (2), (1, 2), (2, 2), (1, 2, 2)$ . Số dãy $x$ tương ứng lần lượt là $1, 2, 1 \cdot 2, 2 \cdot 2, 1 \cdot 2 \cdot 2$ , tổng bằng $13$ .
5 1 2 3 4 5	719	Tổng trên $31$ dãy con không giảm phân biệt.

Bình luận

Không có bình luận tại thời điểm này.