Gợi ý : Bài này có thể làm nhiều cách, cách đơn giản là dùng map để đếm số lượng tất cả các phần tử, dựa vào map đó để chia những phần tử giống nhau vào nhóm hai, còn lại các phần tử riêng biệt vào nhóm một.

Đầu vào

• Dòng đầu tiên là n : số phần tử của mảng

• Dòng thứ 2 là n số nguyên của dãy số

Giới hạn

1<=n<=2.10^5

1<=a[i]<=10^9

Đầu ra

In ra số phần tử tối đa có thể bốc.

Ví dụ :

Input 01

6
1 2 2 3 3 3

Output 01

4

Trong vương quốc Xanadu, công chúa Seraphina đã bị bắt cóc bởi phù thủy ác độc Zarathustra. Zarathustra đã chia nhỏ lời nguyền của mình thành nhiều mảnh và giấu chúng trong các hòn đá ma thuật, rải rác khắp vương quốc. Chỉ có một cách duy nhất để giải lời nguyền và cứu công chúa: tìm ra tất cả các mảnh của lời nguyền và sắp xếp chúng thành một dãy không giảm để kích hoạt phép thuật.

Bạn là anh hùng của vương quốc Xanadu, được giao nhiệm vụ cứu công chúa Seraphina. Bạn đã biết rằng các mảnh của lời nguyền được giấu trong các hòn đá ma thuật, mỗi hòn đá chứa một mảnh của lời nguyền. Bạn có thể chọn một cặp vị trí l và r (1<=l<=r<=n) trong mảng hòn đá và đảo các hòn đá trong đoạn từ l đến r. Nếu tồn tại một cách chọn l, r sao cho các hòn đá sau khi sắp xếp lại thành một dãy không giảm, lời nguyền sẽ được giải.

Gợi ý : Bắt đầu từ vị trí đầu tiên, ta tìm dãy liên tiếp không giảm, giả sử vị trí ta tìm được là l. Sau đó, bắt đầu từ vị trí cuối cùng trở về trước vị trí l, ta tìm vị trí r sao cho [r, n] là đoạn không giảm. Vậy cuối cùng ta chỉ cần kiểm tra đoạn [l, r - 1] có phải là đoạn giảm dần hay không, đoạn này cũng chính là đoạn chúng ta cần phải đảo ngược để cả mảng được sắp xếp. Lưu ý: Chúng ta cũng phải kiểm tra luôn hai đầu mút l và r-1

Đầu vào

• Dòng đầu tiên chứa một số nguyên n - số lượng hòn đá trong vương quốc.

• Dòng thứ hai chứa n số nguyên a[i] - chỉ số của các hòn đá.

Giới hạn

1<=n<=2.10^5

0<=a[i]<=10^9

Đầu ra

In ra "YES" nếu có thể giải lời nguyền và cứu công chúa, ngược lại in ra "NO"

Ví dụ :

Input 01

6
1 3 2 2 4 4

Output 01

YES

Trong một thung lũng xa xôi, có một người anh hùng tên là Aladin đang bắt đầu cuộc hành trình mới. Aladin đã nhận được một bức thư từ vị vua của vương quốc lân cận, đề nghị giúp đỡ trong việc tăng giá trị của dãy số quý giá của vương quốc. Vương quốc đang đối diện với một thách thức kinh khủng - dãy số quý giá của họ đang dần mất đi giá trị. Aladin nhận thấy rằng có thể giúp đỡ, và anh ta quyết tâm đưa dãy số này trở lại vị thế của nó.

Dãy số này được cho bởi n số nguyên a1, a2, ... an, một số nguyên k và một số nguyên h. Mỗi thao tác, Aladin có thể chọn một số nguyên a[i] và tăng giá trị của nó lên 1 đơn vị. Nhiệm vụ của Aladin là tìm giá trị lớn nhất có thể của số lớn thứ h trong dãy sau khi thực hiện không quá k thao tác.

Hãy giúp Aladin hoàn thành nhiệm vụ và mang lại hạnh phúc cho vương quốc!

Đầu vào

Dòng đầu tiên chứa 3 số n, k, h lần lượt là số lượng phần tử trong dãy, số lượng thao tác tối đa và chỉ số của số cần tìm.

Dòng thứ 2 chứa n số nguyên a1, a2,... an

Giới hạn

1<=n<=2.10^5

1<=k<=10^9

1<=h<=n

Đầu ra

In ra màn hình một số nguyên duy nhất là giá trị lớn nhất của số lớn thứ h trong dãy sau khi thực hiện không quá k thao tác.

Ví dụ :

Input 01

5 2 3
1 2 3 4 5

Output 01

4

Giải thích :

Từ dãy ban đầu [1, 2, 3, 4, 5] Aladin có thể tăng a[3] lên 1 đơn vị ta được dãy [1, 2, 4, 4, 5], ở thao tác thứ 2 Aladin tăng a[5] lên 1 đơn vị ta được dãy [1, 2, 4, 4, 6]. Dãy mới có số lớn thứ 3 là 4.

Ở một vương quốc xa xôi, có một chàng hoàng tử tên là Alibaba, người được biết đến với khả năng giải quyết mọi thử thách. Một ngày, Alibaba nhận được một lời thách đấu từ một tên quái vật đầy tham vọng.

Quái vật này tạo ra một câu đố phức tạp cho Alibaba: Hắn ta đưa ra một chuỗi nhị phân gồm các số 0 và 1, độ dài chuỗi là n. Alibaba có k lượng phép thuật giới hạn biến đổi bit 0 thành 1. Sau mỗi lần biến đổi, nếu bit đứng trước bit vừa biến đổi là một bit khác 0, thì bit vừa biến đổi sẽ trở thành số 2, tức là nếu 11 sẽ biến thành 12, nếu 21 thì sẽ thành 22.

Nhiệm vụ của Alibaba là tìm cách biến đổi tối ưu nhất sao cho tổng các số của dãy sau khi biến đổi là lớn nhất có thể.

Alibaba quyết định nhận thách đấu này, và bắt đầu hành trình của mình với hy vọng chiến thắng và bảo vệ vương quốc khỏi sự tàn phá của quái vật. Liệu bạn có thể giúp được Alibaba.

Đầu vào

Dòng đầu tiên gồm n,k - độ dài của chuỗi và số phép biến đổi tối đa.

Dòng thứ hai là chuỗi s ban đầu, gồm các ký tự 0 và 1.

Giới hạn

1<=n<=10^5

0<=k<=n

Đầu ra

In ra tổng lớn nhất có thể đạt được sau khi tối ưu hóa chuỗi.

Ví dụ :

Input 01

5 1
10001

Output 01

4

Ở một thị trấn nhỏ ven biển, có một tên cướp tên là Kasim, người đã đánh cắp một kho báu quý giá từ ngôi nhà của một thương gia giàu có. Sau khi lấy được kho báu, Kasim nhanh chóng bỏ trốn và trốn chạy qua những con đường hẻo lánh. Dù đang bị truy đuổi bởi các thủ lĩnh an ninh, Kasim vẫn không thể từ bỏ kho báu của mình. Anh ấy quyết định trèo lên một dãy đường gạch với độ dài là n, mỗi viên gạch có một màu là a[i].

Tuy nhiên, Kasim biết rằng việc chọn một đường đi ngẫu nhiên có thể dễ dàng bị phát hiện. Do đó, bắt đầu từ vị trí đầu tiên, hắn ta phải nhảy đến những viên gạch bên phải. Ví dụ, nhảy từ viên gạch a[1] đến a[i], a[i] đến a[j] sẽ tạo ra một đường đi a[1] - a[i] - a[j], độ dài đường đi này bằng 3. Đường đi tốt nhất có thể giúp hắn trốn thoát phải là đường đi có viên gạch cuối cùng là a[n] và đường đi phải chia thành các khổi liên tục có độ dài là d, các viên gạch trong khối này phải có cùng màu sắc. Ví dụ với d = 3, đường đi tên cướp chọn có thể là 1, 1, 1, 3, 3, 3.

Liệu tên cướp có trốn thoát thành công hay không? Nếu trốn thoát thành công thì độ dài đường đi ngắn nhất có thể là bao nhiêu?

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n và d - số lượng viên gạch và độ dài của mỗi khối liên tục.

• Dòng thứ hai chứa n số nguyên a1, a2, a3... an - màu của từng viên gạch, trong đó a[i] là màu của viên gạch thứ i.

Giới hạn

2<=n<=2.10^5

1<=d<=n

1<=a[i]<=2.10^5

Đầu ra

In ra một số nguyên là độ dài của đường đi ngắn nhất mà Kasim có thể chọn để trốn thoát. Nếu không có đường đi nào thỏa mãn yêu cầu, in ra -1

Ví dụ :

Input 01

9 3
1 2 2 1 2 1 2 2 2

Output 01

6

Giải thích :

Kasim có thể chọn đường đi a[1] - a[4] - a[6] - a[7] - a[8] -a[9]