{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"Bessie cảm thấy tiếc nuối vì những trò quậy phá mình đã gây ra gần đây ở nông trại, nên đã đồng ý giúp đỡ bác John xếp các đống kiện cỏ khô mới lấy về nông trại.\n\nCô bắt đầu với $N (1 \u003c\u003d N \u003c\u003d 1,000,000, N$ lẻ) đống cỏ trống, được đánh số từ $1$ đến $N$. Sau đó Bác John sẽ đưa cho cô một chuỗi $K$ lệnh (1 \u003c\u003d K \u003c\u003d 25,000), mỗi lệnh có dạng `A B`, nghĩa là Bessie cần chồng thêm một kiện cỏ khô vào đỉnh của mỗi đống trong khoảng từ $A$ đến $B$. Ví dụ, nếu lệnh là `10 13`, thì cô phải thêm một kiện cỏ khô vào mỗi đống số $10, 11, 12$, và $13$.\n\nSau khi Bessie hoàn thành việc xếp cỏ khô theo hướng dẫn, Bác John muốn biết chiều cao trung vị của $N$ đống cỏ khô đó -- tức là, chiều cao của đống ở giữa nếu như các đống được sắp xếp lại theo thứ tự tăng dần (may mắn thay, N là số lẻ, vậy nên đống này là duy nhất). Hãy giúp Bessie trả lời câu hỏi của bác John.\n\n### Dữ liệu\n- Dòng 1: Hai số nguyên cách nhau bởi dấu cách, $N K$.\n- Dòng $2 \\ldots 1+K$: Mỗi dòng chứa một lệnh của bác John dưới dạng hai số nguyên cách nhau bởi dấu cách $A, B$ $(1 \u003c\u003d A \u003c\u003d B \u003c\u003d N)$.\n\n### Kết quả\n- Dòng 1: Chiều cao trung vị của đống sau khi Bessie hoàn thành các lệnh.\n\n### Ví dụ\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 4\n5 5\n2 4\n4 6\n3 5\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n### Giải thích ví dụ\n- Có $N\u003d7$ đống, và $K\u003d4$ lệnh. Lệnh đầu tiên là thêm một kiện cỏ khô vào đống số $5$, lệnh thứ hai là thêm cỏ khô vào các đống $2..4$, v.v.\n\n- Sau khi Bessie hoàn tất, các đống có chiều cao là $0, 1, 2, 3, 3, 1, 0$. Chiều cao trung vị của đống là $1$, vì $1$ là phần tử ở giữa trong thứ tự được sắp xếp $0, 0, 1, 1, 2, 3, 3$."}}]}