LQDOJ Contest #9 - Bài 5 - Chia Dãy

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

Ông Từ đang ôn bài tập về dãy số, hôm nay ông có \(1\) dãy số \(a\) gồm \(n\) phần tử, đối với ông \(1\) dãy con liên tiếp của \(a\) được xem là dãy đẹp nếu số lượng phần tử của dãy con đó không bé hơn giá trị bé nhất trong dãy con và không lớn hơn giá trị lớn nhất trong dãy con.
Hay nói cách khác, đoạn con từ \(i\) đến \(j\) được xem là đẹp nếu \(Min(a_i, a_{i + 1},...a_j) \le j - i + 1 \le Max(a_i, a_{i + 1},...a_j)\). Ông Từ muốn tính số cách chia dãy thành các đoạn đẹp sao cho mỗi phần tử phải thuộc duy nhất \(1\) đoạn đẹp. Vì số cách có thể rất lớn nên bạn hãy in số cách dưới dạng modulo cho \(10^9 + 7\) giúp ông nhé.

Input

  • Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
  • Dòng tiếp theo gồm \(n\) số mô tả mảng \(a\) \((1 \le a_i \le n)\).

Output

  • Gồm \(1\) số nguyên là kết quả bài toán.

Test 1

Input 
7
1 6 2 3 4 3 4
Output 
6
Note

  • Ta có \(6\) cách để chia dãy.

  • [ 1 ] [ 6, 2 ] [ 3, 4, 3, 4 ]

  • [ 1 ] [ 6, 2, 3 ] [ 4, 3, 4 ]
  • [ 1 ] [ 6, 2, 3, 4, 3, 4 ]
  • [ 1, 6 ] [ 2, 3 ] [ 4, 3, 4 ]
  • [ 1, 6, 2 ] [ 3, 4, 3, 4 ]
  • [ 1, 6, 2, 3 ] [ 4, 3, 4 ]

Bình luận