Bài tập

Bé Na có một dãy gồm \(N\) hộp xếp thành hàng ngang, trong đó hộp thứ \(i\) chứa \(A_i\) viên bi (\(0 \leq A_i \leq N\)).

Na thích những dãy hộp mà số bi trong các hộp tăng dần từ trái sang phải. Vì vậy, Na định nghĩa một chỉ số gọi là "độ rối" của dãy hộp: đó là số cặp \((i,j)\) sao cho \(i < j\) nhưng \(A_i > A_j\).

Bây giờ, Na thử một trò chơi: với mỗi giá trị \(j = 0,1,2,\dots,N-1\), Na sẽ giới hạn lại số bi trong các hộp. Cụ thể, những hộp nào đang có nhiều hơn \(j\) viên bi sẽ được giảm xuống còn đúng \(j\) viên. Sau đó, Na muốn biết độ rối của dãy hộp khi áp dụng quy tắc trên.

Với mỗi \(j = 0,1,\dots,N-1\), hãy tính và in ra độ rối của dãy hộp sau khi áp dụng thao tác giới hạn với giá trị \(j\)

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \leq A_i \leq N\)).

Output

• In ra \(N\) dòng, dòng thứ \(j+1\) chứa độ rối của dãy khi sử dụng giá trị \(j\).

Example

5
5 2 3 3 0

0
4
4
5
7

Scoring

• Có \(30\%\) số điểm thỏa mãn \(N \leq 100\).
• Có \(30\%\) số điểm thỏa mãn \(N \leq 5000\).
• Có \(40\%\) số điểm không có ràng buộc gì thêm.

Ở một vùng đất xa xôi nơi mặt trời mọc, có một chàng trai tên là Haruki. Anh sống bình lặng trong một ngôi làng nhỏ, nơi mà mùa xuân luôn thắm sắc hoa anh đào. Một ngày nọ, Haruki đem lòng yêu một thiếu nữ tên là Aika --- người con gái dịu dàng như làn sương sớm.

Để bày tỏ tình yêu của mình, Haruki quyết định rời làng và bước vào hành trình thu thập các loại đá quý kỳ diệu, rải rác trên con đường dẫn đến Đỉnh Mặt Trăng --- nơi truyền thuyết kể rằng có thể rèn nên món trang sức thiêng liêng chỉ khi hội đủ những viên đá mang tần số hoàn hảo.

Dọc theo hành trình, Haruki thu thập được một chuỗi \(N\) viên đá quý, viên thứ \(i\) thuộc loại \(a_i\). Tuy nhiên, chỉ một số tổ hợp đá nhất định mới có thể hòa hợp để tạo nên món trang sức thần kỳ. Haruki có thể đem cắt bỏ một vài viên đá ở đầu hoặc ở cuối chuỗi. Sau khi cắt, thì chuỗi đá quý của anh phải là một chuỗi đá thiêng.

Một tổ hợp đá là "thiêng" nếu tồn tại:

• Ít nhất một loại đá xuất hiện đúng \(1\) lần,
• Ít nhất một loại xuất hiện đúng \(2\) lần,
• …
• Ít nhất một loại đá xuất hiện đúng \(K\) lần.

Hãy giúp Haruki đếm xem có bao nhiêu cách lựa chọn đoạn liên tiếp trong dãy đá quý sao cho tổ hợp đá còn lại là một tổ hợp thiêng liêng, đủ để rèn món trang sức định mệnh cho Aika.

Input

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) \((1 \leq N \leq 10^5)\) và \(K\) \((1 \leq K \leq 4)\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq N)\) --- đại diện cho loại đá quý mà Haruki tìm thấy.

Output

In ra một số nguyên duy nhất --- số cách Haruki có thể chọn đoạn đá thoả điều kiện "thiêng".

Hai lựa chọn khác nhau nếu có ít nhất một vị trí được giữ lại trong một lựa chọn nhưng bị loại bỏ trong lựa chọn kia.

Example

6 2
5 4 5 2 6 5

5

3 1
1 2 1

6

Scoring

• Subtask 1 (14 điểm): \(N \leq 1000\)
• Subtask 2 (16 điểm): \(1 \leq a_i \leq K\) với mọi \(i\)
• Subtask 3 (32 điểm): \(K = 1\)
• Subtask 4 (38 điểm): Không có ràng buộc bổ sung

Cho dãy số nguyên dương \(A = (a_1, a_2, ..., a_n)\).

Hãy đếm xem có bao nhiêu cặp số bằng nhau trong dãy \(A\).

Input

**Dữ liệu vào: ** Dữ liệu vào từ tệp văn bản CSBN.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên dương \(n (n \leq 10^6)\).
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2, ..., a_n (a_i \leq 10^9, i = 1, 2, 3, ..., n)\), các số được ghi cách nhau một dấu cách trống.

Output

**Dữ liệu ra: ** Ghi vào tệp văn bản CSBN.OUT ghi duy nhất một số là kết quả tìm được

Example

5
10 9 6 5 9

1

6
10 11 12 11 11 15

3

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm của bài có \(n \leq 10^3\).
• Có \(60\%\) số test tương ứng với \(60\%\) số điểm của bài có \(n > 10^3\) và \(a_i \leq 10^6\).

Bạn được cung cấp một bức ảnh có kích thước \(n \times m\) điểm ảnh. Mỗi điểm ảnh là màu trắng hoặc đen.

Nhiệm vụ của bạn là thay đổi càng ít điểm ảnh càng tốt để bức ảnh trở thành một mã vạch hợp lệ.

Một bức ảnh được xem là mã vạch nếu thỏa mãn hai điều kiện sau:

• Mỗi cột chỉ có một màu duy nhất (hoặc toàn trắng, hoặc toàn đen).
• Khi nhóm các cột liền kề có cùng màu lại, kích thước của mỗi nhóm phải nằm trong đoạn \([x, y]\).

Mục tiêu: Tìm số điểm ảnh ít nhất cần tô lại để bức ảnh trở thành mã vạch hợp lệ.

\InputFile

• Dòng đầu tiên chứa bốn số nguyên \(n, m, x, y\) (\(1 \le n \times m \le 10^6, x \le y \le 10^6\)).
• Tiếp theo là \(n\) dòng, mỗi dòng gồm đúng \(m\) ký tự, mô tả bức ảnh ban đầu.
• Mỗi ký tự là '.' (điểm trắng) hoặc # (điểm đen).

\OutputFile

In ra một số nguyên duy nhất --- số điểm ảnh ít nhất cần tô lại. Đảm bảo rằng luôn tồn tại cách làm thỏa mãn yêu cầu.

\Scoring

• Subtask 1 (22 điểm): \(n \cdot m \le 20\)
• Subtask 2 (18 điểm): Tất cả các ô đều có màu trắng.
• Subtask 3 (30 điểm): \(m \le 1000\)
• Subtask 4 (30 điểm): Không có giới hạn gì thêm

Example

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

11

2 5 1 1
#####
.....

5