Zing MP3 là ứng dụng nghe nhạc trực tuyến hàng đầu Việt Nam hiện nay. Với kho nhạc phong phú, đa dạng và cập nhật liên tục, Zing MP3 đem đến cho người dùng những trải nghiệm âm nhạc tuyệt vời nhất. Ngoài ra, Zing MP3 còn kết nối được với trợ lý ảo Kiki (The Voice Assistant for Vietnamese) để người dùng có thể tương tác với ứng dụng bằng giọng nói. Một thuật toán đánh giá mức độ yêu thích của bài hát được đội ngũ phát triển của Zing MP3 đề xuất như sau.

Thông tin về số lượt thả tim của người nghe cho một bài hát được biểu diễn bằng một mảng A gồm N số nguyên, trong đó giá trị phần tử $A[i], (0 \leq i < N)$ là số lượt thả tim của người nghe tại giây thứ i của bài hát.

Biết rằng các bài hát sẽ có thời lượng khác nhau, nên để chuẩn hóa dữ liệu, mảng A sẽ được biến đổi thành mảng B gồm M số nguyên. Các phần tử của mảng B được xác định theo công thức: $B[i] = A[i \text{ mod } N]$ với $0 \leq i < M$. Mảng B này sẽ được sử dụng để đánh giá mức độ yêu thích của bài hát.

Một mảng con $[l,r]$ có độ dài lớn hơn hoặc bằng K được gọi là ấn tượng nếu có thể sắp xếp lại vị trí các phần tử của nó sao cho mảng con đó trở thành dãy tăng ngặt.

Hãy giúp đội ngũ phát triển của Zing MP3 đếm số lượng mảng con ấn tượng của mảng B.

Ghi chú: Mảng con $[l,r]$ được gọi là tăng ngặt nếu $B[l] < B[l+1] < ... < B[r]$.

Đầu vào:

• Dòng đầu tiên gồm ba số nguyên $N, M, K$. Trong đó $N$ là độ dài mảng A, M là độ dài mảng B, và K là độ dài tối thiểu của một mảng con ấn tượng.
• Dòng tiếp theo gồm N số nguyên là các phần tử của mảng A.

Giới hạn

• $1 \leq K \leq M$
• $0 \leq A[i] \leq 10^9$
• $25\%$ số test có $1 \leq N \leq 100, 1 \leq M \leq 100$
• $75\%$ số test còn lại có $1 \leq N \leq 3.10^5, 1 \leq M \leq 3.10^5$

Đầu ra:

• In ra một số nguyên duy nhất là số lượng mảng con ấn tượng của mảng B.

Giải thích: Ví dụ 1: Mảng B là $[1,2,1,1]$, có hai mảng con ấn tượng là $[1,2]$ và $[2,1]$.

Ví dụ 2: Mảng B là $[1,2,1]$, có hai mảng con ấn tượng là $[1,2]$ và $[2,1]$.

Ví dụ 1:

Đầu vào:

3 4 2
1 2 1

Đầu ra:

2

Ví dụ 2:

Đầu vào:

4 3 2
1 2 1 1

Đầu ra:

2