CSES - Increasing Subsequence II | Dãy con tăng II

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
letangphuquy
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho trước một mảng gồm \(n\) số nguyên, bạn cần tính số lượng dãy con tăng mà nó chứa. Nếu hai dãy con có các giá trị giống nhau nhưng ở những vị trí khác nhau trong mảng, chúng được tính là khác nhau.

Input

Dòng đầu tiên chứa số nguyên \(n:\) kích thước của mảng.

Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n:\) nội dung của mảng.

Output

In ra một số nguyên là số lượng dãy con tăng theo modulo \(10^9 + 7\).

Constraints

  • \(1≤n≤2⋅10^5\)
  • \(1≤x_i≤10^9\)

Example

Sample Input:

3
2 1 3

Sample Output:
5

Note

Các dãy con tăng là \([2], [1], [3], [2,3]\) và \([1,3]\).

Bình luận