Búp bê nga

View as PDF

Submit solution

Points: 0.78 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Lê Yên Thanh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Búp bê Nga hay Búp bê babushka (Búp bê lồng nhau, Búp bê làm tổ, ...) là một loại búp bê đặc trưng của Nga. Thật ra đó là một bộ gồm những búp bê rỗng ruột có kích thước từ lớn đến nhỏ. Con búp bê nhỏ nhất sẽ được chứa đựng trong lòng con búp bê lớn hơn nó một chút, đến lượt mình con búp bê lớn được chứa trong một con búp bê khác lớn hơn, và cứ thế cho đến con lớn nhất sẽ chứa tất cả những con búp bê còn lại trong bộ.

Hôm nay yenthanh132 mời bạn đến tham quan bố sưu tập búp bê nga của anh ta. Nhưng việc tham quan chỉ là phụ thôi, việc chính là yenthanh132 muốn đố bạn một bài toán liên quan đến những con búp bê nga này.

Đầu tiên yenthanh132 sắp xếp ~N~ con búp bê của anh ta từ trái sang phải theo một thứ tự bất kì, con thứ ~i~ có kích thước ~a_{i}~ ~(1 \leq a_{i} \leq M)~. Sau đó anh ta yêu cầu bạn tạo khoảng trống ở đầu mút trái, để làm được điều đó, bạn cần xếp những con búp bê có kích thước nhỏ hơn ở bên trái đặt vào những con búp bê có kích thước lớn hơn bên phải, tuy nhiên mỗi con búp bê lớn hơn chỉ chứa đúng ~1~ con búp bê nhỏ hơn nó. Bạn chỉ được quyền dùng ~3~ thao tác: Lấy một con búp bê ở bên trái lên, di chuyển nó sang phải và đặt vào bên trong một con búp bê lớn hơn. Bạn cần tìm cách sắp xếp sao cho khoảng trống ở đầu mút trái là lớn nhất.

Nói cách khác, yenthanh132 yêu cầu bạn tìm một số nguyên ~K~ lớn nhất ~(1 \leq K \leq \frac{N}{2})~ sao cho ~K~ con búp bê trái nhất có để đặt vào bên trong ~K~ con búp bê ngay sau đó (từ ~k + 1~ ...~k \times 2)~, mỗi con búp bê chỉ chứa đúng ~1~ con búp bê, theo một thứ tự nào đó. Lưu ý con búp bê ~i~ có thể đặt vào bên trong con búp bê ~j~ nếu ~(a_{i} < a_{j})~.

Input

  • Dòng đầu tiên có ~2~ số ~N~, ~M~ lần lượt là số lượng con búp bê của yenthanh132 và kích thước giới hạn của ~N~ con búp bê đó. ~N~ luôn là số chẵn.
  • Dòng thứ ~2~ chứa ~N~ số ~a_{i}~, là kích thước của ~N~ con búp bê từ trái sang phải. ~(1 \leq a_{i} \leq M)~.

Output

  • Xuất ra số ~K~ theo yêu cầu của bài. Nếu không có kết quả (không có cách sắp nào để tạo khoảng trống ở đầu mút trái) thì xuất ra ~-1~.

Giới hạn

  • ~20\%~ test đầu có ~(1 \leq N \leq 100~; ~1 \leq M \leq 1000)~.
  • ~20\%~ test tiếp theo có ~(1 \leq N \leq 10000~; ~1 \leq M \leq 1000)~.
  • ~60\%~ test còn lại có ~(1 \leq N \leq 10^{5}~; ~1 \leq M \leq 10^{5})~.

Sample Input 1

10 5
2 1 4 2 3 2 4 5 2 3

Sample Output 1

4

Sample Input 2

4 5
2 2 1 1

Sample Output 2

-1

Note

Giải thích ví dụ đầu tiên: Ta có thể đặt ~4~ con búp bê bên trái vào trong ~4~ con búp bê bên cạnh theo thứ tự như sau:

~1~ đặt vào ~5~, ~2~ đặt vào ~6~, ~3~ đặt vào ~8~, ~4~ đặt vào ~7~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.