{"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":"Bạn đang làm việc cho công ty Bờ Lóc Trên trong phòng ban cấu trúc dữ liệu. Sau khi không thành công với nhiệm vụ trước về việc chèn khóa, bạn được yêu cầu viết một cấu trúc dữ liệu mới có khả năng trả về nhanh chóng các thống kê thứ tự k-trong một phân đoạn của mảng.\n\nNghĩa là, với một mảng a[1 ... n] chứa các số nguyên khác nhau, chương trình của bạn phải trả lời một loạt các câu hỏi Q(i, j, k) theo dạng: \"Nếu phân đoạn a[i ... j] được sắp xếp, thì số thứ k trong phân đoạn đó sẽ là gì?\"\n\nVí dụ, giả sử mảng a \u003d (1, 5, 2, 6, 3, 7, 4). Hãy xem câu hỏi Q(2, 5, 3). Phân đoạn a[2 ... 5] là (5, 2, 6, 3). Nếu chúng ta sắp xếp phân đoạn này, ta được (2, 3, 5, 6), số thứ ba là 5, và do đó câu trả lời cho câu hỏi là 5.\n\nĐầu vào\nDòng đầu tiên của đầu vào chứa n - kích thước của mảng và m - số lượng câu hỏi cần trả lời (1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000).\n\nDòng thứ hai chứa n số nguyên khác nhau không vượt quá 10^9 theo giá trị tuyệt đối - mảng mà câu trả lời được cung cấp cho.\n\nMỗi dòng tiếp theo chứa mô tả câu hỏi, mỗi mô tả gồm ba số: i, j và k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) và đại diện cho câu hỏi Q(i, j, k).\n\nĐầu ra\nĐối với mỗi câu hỏi, in ra câu trả lời cho nó - số thứ k trong phân đoạn đã sắp xếp a[i ... j].\n \u003cdiv\u003e\u003ch3\u003eVí dụ\u003c/h3\u003e\n \u003cpre\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\n7 3\n1 5 2 6 3 7 4\n2 5 3\n4 4 1\n1 7 3\n\n\u003cstrong\u003eOutput:\u003c/strong\u003e\n5\n6\n3\n\u003c/pre\u003e\n\u003c/div\u003e"}}]}