Bài tập

Anh An là nhân viên kỹ thuật trong nhà máy X trên địa bàn tỉnh. Nhà máy được trang
bị dây chuyền sản xuất hiện đại, tất cả các sản phẩm khi đi qua băng chuyền được máy tính
đánh mã loại và lưu lại. Sản phẩm thứ i đi qua băng chuyền được gán bởi một số nguyên
đương \(a_{i}\) là mã loại tương ứng (các sản phẩm giống nhau thì có cùng một mã loại). Trong
một công đoạn sản xuất, có \(n\) sản phẩm đi qua băng chuyền được máy tính đánh mã loại và
lưu lại thành một dãy \(A\) gồm các số nguyên dương \(a_{1}, a_{2}, ...,a_n\). Kết thúc công đoạn, lãnh
đạo công ty yêu cầu anh An báo cáo số lượng tất cả các dãy con của dãy \(A\) thỏa mãn có ít
nhất \(k\) sản phẩm cùng mã loại \((1 \leq k \leq n)\), với dãy con là dãy được tạo từ các phần tử liên
tiếp của dãy \(A\).

Bạn hãy viết chương trình giúp anh An giải quyết bài toán trên.

Yêu cầu: Đưa ra số lượng tất cả các dãy con của dãy \(A\) có ít nhất \(k\) sản phẩm cùng mã loại.

Input

Từ tệp văn bản TKSP.INP gồm:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n, k\) \((1 \leq k \leq n \leq 4 \times 10^5)\)
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, ...,a_n (1 \leq a \leq 10^6)\)

Các số trên một dòng cách nhau bởi một dấu cách trống.

Output

Ghi ra tệp văn bản TKSP.OUT gồm một dòng chứa một số nguyên dương
thỏa mãn yêu câu bài toán.

Example

5 2
1 2 1 2 1

6

Scoring

• \(40\%\) số test với \(1 \leq n \leq 10^3\)
• \(40\%\) số test với \(10^3 < n \leq 10^4\)
• \(20\%\) số test với \(10^4 < n \leq 4 \times 10^5\)

Quân đang đi vượt ải Codeforces. Để trở thành master, Quân phải vượt qua \(n\) con quái vật. Con quái vật thứ \(i\) sẽ làm Quân hao tổn \(a_i\) công lực. Và vì các ải này diễn ra liên tiếp, Quân không có thời gian để hồi phục công lực. Quân sẽ gục ngã nếu sau một trận chiến, công lực còn lại bé hơn hoặc bằng \(0\).

Ví dụ: nếu ban đầu Quân có \(10\) công lực, và con quái vật đầu tiên có sức mạnh \(a_1 = 4\), Quân sẽ vượt ải thành công và còn \(6\) công lực. Nếu con quái vật thứ hai có sức mạnh ít nhất là \(6\), Quân sẽ bị đánh gục ở ải này.

Quân đã nghiên cứu rất kỹ về đối thủ của mình. Anh biết rằng sức mạnh của chúng tương ứng là \(a_1, a_2, ..., a_n\). Và để thêm phần kỹ càng, Quân sẽ mang theo một bộ giáp có thể chống được \(k\) sát thương. Nói cách khác, nếu Quân sử dụng bộ giáp này khi đấu với quái vật thứ \(i\) thì chỉ mất đi \(max(0, a_i - k)\) công lực. Tuy nhiên, bộ giáp này chỉ sử dụng được cho \(1\) ải duy nhất và Quân phải tính toán sử dụng sao cho tối ưu.

Quân muốn vượt qua cả \(n\) ải này. Hỏi ban đầu anh phải chuẩn bị ít nhất bao nhiêu công lực? Biết rằng Quân rất bá đạo nên sẽ sử dụng giáp một cách tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, k \ (k \leq 10^9)\) tương ứng là số quái vật và sức mạnh của giáp.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\) là sức mạnh của \(n\) con quái vật.

Output

In ra một số nguyên là công lực ít nhất Quân cần chuẩn bị trước khi vượt ải.

Example

5 5
1 2 6 7 3

15

5 3
1 1 1 1 1

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^5\).

Sau khi hoàn thành bài thi, Alice, Bob cùng các bạn thi lập trình tham quan trại nghiên tại công viên ánh sáng. Công viên có một dàn đèn gồm \(n\) bóng đèn được đặt vị trí theo phương ngang. Các đèn đánh số thứ tự từ \(1\) đến \(n\) theo hướng từ trái sang phải. Mỗi bóng đèn có ánh sáng xanh hoặc màu đỏ.

Nhìn vào dàn đèn với ánh sáng màu xanh, màu đỏ rực rỡ, Alice đã yêu cầu Bob trả lời câu hỏi:

Nếu phải chọn \(k\) bóng đèn kề nhau và đổi trạng thái màu của các bóng đèn đó (màu xanh chuyển sang màu đỏ, màu đỏ chuyển sang màu xanh) thì số lượng bóng đèn màu xanh trên dàn đèn nhiều nhất là bao nhiêu?

Input

Dữ liệu: Cho từ tệp vào DANDEN.INP gồm:

• Dòng thứ nhất ghi hai số nguyên dương \(n, k\) (\(3 \le n \le 10^6; 1 \le k \le n\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0\) biểu thị đèn màu đỏ, \(1\) biểu thị đèn màu xanh).

Output

Kết quả: Ghi ra tệp DANDEN.OUT gồm một số nguyên là số bóng đèn màu xanh lớn nhất có thể đạt được.

Example

8 2
1 1 0 0 0 1 1 0

6

8 2
1 1 1 1 1 1 1 1

8

8 2
1 0 1 0 1 0 1 1

5

Scoring

Giới hạn:

• 40% test ứng với \(k = 1\).
• 40% test ứng với \(k = 2\).
• 20% test còn lại không giới hạn gì thêm.

Cho một dãy \(A\) gồm \(n\) số nguyên dương \(A_1\), \(A_2\), \(A_3\), ..., \(A_n\). Có bao nhiêu cặp chỉ số \((i,j)\) thỏa mãn \(1 \leq i < j \leq n\) để tổng \(A_i+A_j\) chia hết cho \(3\).

Input

Dữ liệu vào: Đọc từ tệp dayso.inp gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \leq n \leq 10^5)\).
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(A_1, A_2, A_3, ..., A_n\), mỗi số không vượt quá \(10^9\), giữa hai số cách nhau \(1\) dấu cách.

Output

Dữ liệu ra: Ghi ra tệp dayso.out một dòng duy nhất là số cặp tìm được.

Example

7
3 1 2 9 5 3 5

6

Scoring

• \(70\%\) số điểm có \(n \leq 10^4\).
• \(30\%\) số điểm còn lại không có ràng buộc gì thêm.