NTSEQ - Số lượng dãy con tăng
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Cho dãy số a 1 ,a 2 ,a 3 ,...,a n . Hãy đếm số lượng dãy con tăng dài nhất của dãy số trên.
Một dãy con độ dài k của dãy a được xác định bởi một bộ chỉ số (u 1 ≤u 2 ≤u 3 ≤...≤u k ) (1≤u i ≤n). Hai dãy con (u 1 ,u 2 ,u 3 ,...,u k ) và (v 1 ,v 2 ,v 3 ,...,v t ) được gọi là khác nhau nếu k≠t hoặc tồn tại một vị trí i sao cho u i ≠v i .
Input
- Dòng đầu tiên ghi số nguyên dương n (n≤10 5 )
- Dòng tiếp theo ghi n số nguyên mô tả dãy a (a i ≤10 9 )
Output
- Một dòng duy nhất ghi kết quả theo module 1000000007
Example
Input:
6
1 1 2 2 3 3
Output:
8
- Người up: iamtnl