Bài 11.1. Thống Kê Chuỗi Điểm Đặc Biệt - [Độ khó: Khá]

Mô tả bài tập: Bạn là trợ lý của một giáo sư thống kê, người đang nghiên cứu về xu hướng học tập của sinh viên. Giáo sư cung cấp cho bạn một chuỗi điểm số các bài kiểm tra liên tiếp của một sinh viên (ví dụ: điểm bài 1, bài 2, ..., bài N). Ông muốn bạn tìm và thống kê tất cả các "chuỗi điểm đặc biệt" – tức là các chuỗi điểm con liên tiếp không giảm có độ dài tối thiểu là K. Nhiệm vụ của bạn là đếm xem có bao nhiêu chuỗi điểm đặc biệt như vậy.

Ví dụ: Nếu chuỗi điểm là [1, 2, 3, 2, 4, 5] và K = 3:

• [1, 2, 3] là chuỗi đặc biệt (dài 3, không giảm).
• [2, 4, 5] là chuỗi đặc biệt (dài 3, không giảm).
• [1, 2, 3, 2] không phải là chuỗi đặc biệt (bị giảm ở cuối).
• [1, 2] không phải là chuỗi đặc biệt (dài < K).
• [4, 5] không phải là chuỗi đặc biệt (dài < K).

INPUT FORMAT Dòng đầu tiên chứa hai số nguyên N và K (1 <= K <= N <= 10^5). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (0 <= a_i <= 1000) là các điểm số của sinh viên.

OUTPUT FORMAT In ra một số nguyên duy nhất là tổng số lượng chuỗi điểm đặc biệt tìm được.

Ví dụ: Input:

6 3
1 2 3 2 4 5

Output:

2

Giải thích:

• Mảng điểm là [1, 2, 3, 2, 4, 5], K = 3.
• Ta tìm các chuỗi con liên tiếp không giảm:
  • Bắt đầu từ 1: [1, 2, 3]. Đây là một chuỗi không giảm, độ dài 3 (>=K). Cộng 1 vào kết quả. Tiếp tục từ [1, 2, 3], nếu thêm 2 vào ta có [1, 2, 3, 2]. Chuỗi này bị giảm ở cuối (3 > 2) nên dừng.
  • Bắt đầu từ 2 (sau khi chuỗi không giảm trước đó bị phá vỡ): [2, 4, 5]. Đây là một chuỗi không giảm, độ dài 3 (>=K). Cộng 1 vào kết quả. Tiếp tục từ [2, 4, 5], không còn phần tử nào.
• Tổng cộng có 2 chuỗi điểm đặc biệt được tìm thấy.