#1331. INCSEQ - Số dãy con

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Bài tập thầy Nguyễn Thanh Bình Ôn ĐT Hải Phòng T10/2020

Cho dãy số nguyên a_1, a_2, \dots, a_n\ (|a_i| ≤ 10^9, 1 ≤ n ≤ 10^5) . Dãy con tăng dần độ dài k của dãy số này là bộ chỉ số i_1, i_2, \dots, i_k thỏa mãn các điều kiện:

  • 1 ≤ i_1 < i_2 < i_3 < \dots <i_k ≤ n :
  • a_{i_1}<a_{i_2}<\dots <a_{i_k} .

Yêu cầu: Hãy tìm số lượng các dãy con tăng dần độ dài lớn nhất khác nhau của dãy số cho trước và đưa ra phần dư của số tìm được khi chia cho 10^9+7 . Hai dãy con được gọi là khác nhau nếu như bộ chỉ số các phần tử khác nhau.

Dữ liệu vào:

  • Dòng đầu tiên 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:

  • Giá trị tìm được.

Ví dụ:

Dữ liệu vào:
6
1 1 2 2 3 3
Dữ liệu ra:
8

Giới hạn:

  • 60\% số test có n≤100 .