Dãy "chia tay"

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

Cho dãy \(a\) gồm \(n\) phần tử \(a_1,a_2,...,a_n\). Hỏi dãy \(a\) đó có tất cả bao nhiêu dãy con "chia tay", biết rằng dãy con "chia tay" là dãy gồm \(c\) phần tử liên tiếp và mỗi phần tử của dãy đó đều không quá \(t\).

Input

  • Dòng thứ nhất chứa \(3\) số nguyên \(n,t,c(1\le n\le 2.10^5,0\le t\le 10^9,1\le c\le n)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(0\le a_i\le 10^9)\)

Output

  • In ra số lượng dãy con "chia tay" có trong dãy \(a\)

Example

Test 1

Input 
4 2 2
1 0 1 0
Output 
3
Note

Giải thích: \(3\) dãy con "chia tay" đó là: \([1,0],[0,1],[1,0]\)

Bình luận