#include <iostream>
#include <vector>
#include <algorithm>
int allocArray[1'660'965 + 100'000];
int allocIndex = 0;
int* NewInt(int size) noexcept {
 int* ret = allocArray + allocIndex;
 allocIndex += size;
 return ret;
}
struct Range {
 int start, end;
 bool Include(Range outer) const noexcept { return outer.start <= start && end <= outer.end; }
 bool Exclude(Range outer) const noexcept { return outer.end < start || end < outer.start; }
 bool IsLeaf() const noexcept { return start == end; }
 int Count() const noexcept { return 1 + end - start; }
};
class Node {
public:
 inline static int* InitArray;
public:
 explicit Node(Range r) noexcept : range(r) {
 if (range.IsLeaf()) {
 (array = NewInt(n = 1))[0] = InitArray[range.start];
 return;
 }
 int mid = range.start + (range.end - range.start) / 2;
 left = new Node({ range.start, mid });
 right = new Node({ mid + 1, range.end });
 array = NewInt(n = range.Count());
 std::merge(left->array, left->array + left->n, right->array, right->array + right->n, array);
 }
 ~Node() {
 delete left;
 delete right;
 }
 int LessCount(Range query, int value) const noexcept {
 if (range.Exclude(query)) { return 0; }
 if (range.Include(query)) {
 return static_cast<int>(std::lower_bound(array, array + n, value) - array);
 }
 return left->LessCount(query, value) + right->LessCount(query, value);
 }
 int GetMinimum() const noexcept { return array[0]; }
 int GetMaximum() const noexcept { return array[n-1]; }
private:
 Range range;
 Node* left = nullptr, * right = nullptr;
 int* array;
 int n;
};
int main() noexcept {
 std::cin.tie(nullptr)->sync_with_stdio(false);
 int n, q;
 std::cin >> n >> q;
 Node::InitArray = NewInt(n);
 for (int i = 0; i < n; ++i) {
 std::cin >> Node::InitArray[i];
 }
 Node* const root = new Node({ 0, n - 1 });
 const int minValue = root->GetMinimum();
 const int maxValue = root->GetMaximum();
 for (int i = 0; i < q; ++i) {
 int l, r, k;
 std::cin >> l >> r >> k;
 const Range query{ l - 1, r - 1 };
 int low = minValue;
 for (int high = maxValue, mid; low < high; ) {
 mid = low + (high - low) / 2;
 if (root->LessCount(query, mid + 1) < k) {
 low = mid + 1;
 }
 else {
 high = mid;
 }
 }
 std::cout << low << '\n';
 }
 return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKaW50IGFsbG9jQXJyYXlbMSc2NjAnOTY1ICsgMTAwJzAwMF07CmludCBhbGxvY0luZGV4ID0gMDsKaW50KiBOZXdJbnQoaW50IHNpemUpIG5vZXhjZXB0IHsKICAgIGludCogcmV0ID0gYWxsb2NBcnJheSArIGFsbG9jSW5kZXg7CiAgICBhbGxvY0luZGV4ICs9IHNpemU7CiAgICByZXR1cm4gcmV0Owp9CgpzdHJ1Y3QgUmFuZ2UgewogICAgaW50IHN0YXJ0LCBlbmQ7CiAgICBib29sIEluY2x1ZGUoUmFuZ2Ugb3V0ZXIpIGNvbnN0IG5vZXhjZXB0IHsgcmV0dXJuIG91dGVyLnN0YXJ0IDw9IHN0YXJ0ICYmIGVuZCA8PSBvdXRlci5lbmQ7IH0KICAgIGJvb2wgRXhjbHVkZShSYW5nZSBvdXRlcikgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gb3V0ZXIuZW5kIDwgc3RhcnQgfHwgZW5kIDwgb3V0ZXIuc3RhcnQ7IH0KICAgIGJvb2wgSXNMZWFmKCkgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gc3RhcnQgPT0gZW5kOyB9CiAgICBpbnQgQ291bnQoKSBjb25zdCBub2V4Y2VwdCB7IHJldHVybiAxICsgZW5kIC0gc3RhcnQ7IH0KfTsKY2xhc3MgTm9kZSB7CnB1YmxpYzoKICAgIGlubGluZSBzdGF0aWMgaW50KiBJbml0QXJyYXk7CgpwdWJsaWM6CiAgICBleHBsaWNpdCBOb2RlKFJhbmdlIHIpIG5vZXhjZXB0IDogcmFuZ2UocikgewogICAgICAgIGlmIChyYW5nZS5Jc0xlYWYoKSkgewogICAgICAgICAgICAoYXJyYXkgPSBOZXdJbnQobiA9IDEpKVswXSA9IEluaXRBcnJheVtyYW5nZS5zdGFydF07CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIGludCBtaWQgPSByYW5nZS5zdGFydCArIChyYW5nZS5lbmQgLSByYW5nZS5zdGFydCkgLyAyOwogICAgICAgIGxlZnQgPSBuZXcgTm9kZSh7IHJhbmdlLnN0YXJ0LCBtaWQgfSk7CiAgICAgICAgcmlnaHQgPSBuZXcgTm9kZSh7IG1pZCArIDEsIHJhbmdlLmVuZCB9KTsKCiAgICAgICAgYXJyYXkgPSBOZXdJbnQobiA9IHJhbmdlLkNvdW50KCkpOwogICAgICAgIHN0ZDo6bWVyZ2UobGVmdC0+YXJyYXksIGxlZnQtPmFycmF5ICsgbGVmdC0+biwgcmlnaHQtPmFycmF5LCByaWdodC0+YXJyYXkgKyByaWdodC0+biwgYXJyYXkpOwogICAgfQogICAgfk5vZGUoKSB7CiAgICAgICAgZGVsZXRlIGxlZnQ7CiAgICAgICAgZGVsZXRlIHJpZ2h0OwogICAgfQogICAgaW50IExlc3NDb3VudChSYW5nZSBxdWVyeSwgaW50IHZhbHVlKSBjb25zdCBub2V4Y2VwdCB7CiAgICAgICAgaWYgKHJhbmdlLkV4Y2x1ZGUocXVlcnkpKSB7IHJldHVybiAwOyB9CiAgICAgICAgaWYgKHJhbmdlLkluY2x1ZGUocXVlcnkpKSB7CiAgICAgICAgICAgIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6bG93ZXJfYm91bmQoYXJyYXksIGFycmF5ICsgbiwgdmFsdWUpIC0gYXJyYXkpOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGxlZnQtPkxlc3NDb3VudChxdWVyeSwgdmFsdWUpICsgcmlnaHQtPkxlc3NDb3VudChxdWVyeSwgdmFsdWUpOwogICAgfQogICAgaW50IEdldE1pbmltdW0oKSBjb25zdCBub2V4Y2VwdCB7IHJldHVybiBhcnJheVswXTsgfQogICAgaW50IEdldE1heGltdW0oKSBjb25zdCBub2V4Y2VwdCB7IHJldHVybiBhcnJheVtuLTFdOyB9CnByaXZhdGU6CiAgICBSYW5nZSByYW5nZTsKICAgIE5vZGUqIGxlZnQgPSBudWxscHRyLCAqIHJpZ2h0ID0gbnVsbHB0cjsKICAgIGludCogYXJyYXk7CiAgICBpbnQgbjsKfTsKCmludCBtYWluKCkgbm9leGNlcHQgewogICAgc3RkOjpjaW4udGllKG51bGxwdHIpLT5zeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgaW50IG4sIHE7CiAgICBzdGQ6OmNpbiA+PiBuID4+IHE7CgogICAgTm9kZTo6SW5pdEFycmF5ID0gTmV3SW50KG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBzdGQ6OmNpbiA+PiBOb2RlOjpJbml0QXJyYXlbaV07CiAgICB9CgogICAgTm9kZSogY29uc3Qgcm9vdCA9IG5ldyBOb2RlKHsgMCwgbiAtIDEgfSk7CgogICAgY29uc3QgaW50IG1pblZhbHVlID0gcm9vdC0+R2V0TWluaW11bSgpOwogICAgY29uc3QgaW50IG1heFZhbHVlID0gcm9vdC0+R2V0TWF4aW11bSgpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcTsgKytpKSB7CiAgICAgICAgaW50IGwsIHIsIGs7CiAgICAgICAgc3RkOjpjaW4gPj4gbCA+PiByID4+IGs7CiAgICAgICAgY29uc3QgUmFuZ2UgcXVlcnl7IGwgLSAxLCByIC0gMSB9OwoKICAgICAgICBpbnQgbG93ID0gbWluVmFsdWU7CiAgICAgICAgZm9yIChpbnQgaGlnaCA9IG1heFZhbHVlLCBtaWQ7IGxvdyA8IGhpZ2g7ICkgewogICAgICAgICAgICBtaWQgPSBsb3cgKyAoaGlnaCAtIGxvdykgLyAyOwogICAgICAgICAgICBpZiAocm9vdC0+TGVzc0NvdW50KHF1ZXJ5LCBtaWQgKyAxKSA8IGspIHsKICAgICAgICAgICAgICAgIGxvdyA9IG1pZCArIDE7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBoaWdoID0gbWlkOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHN0ZDo6Y291dCA8PCBsb3cgPDwgJ1xuJzsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==

comments (?)

NyAzCjEgNSAyIDYgMyA3IDQKMiA1IDMKNCA0IDEKMSA3IDM=

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

5
6
3

https://ideone.com/tocGa0

Share or Embed source code

<script src="https://ideone.com/e.js/tocGa0" type="text/javascript" ></script>

Global

Ace editor

Textarea