import java.io.*;
import java.util.*;
/**
* @username: sriman_chetan
* @author: Chetan Raikwar
* @date: 28-10-2020
*/
class Solution {
int n
= Integer.
parseInt(input.
nextToken()); int m
= Integer.
parseInt(input.
nextToken());
Pair[] a = new Pair[n];
for (int i = 0; i < n; i++) {
int num
= Integer.
parseInt(input.
nextToken()); a[i] = new Pair(num, i);
}
MergesortTree mergesortTree = new MergesortTree(a, n);
//mergesortTree.showTree();
while (m-- > 0) {
int i
= Integer.
parseInt(input.
nextToken()); int j
= Integer.
parseInt(input.
nextToken()); int k
= Integer.
parseInt(input.
nextToken());
k = (k > (j - i + 1)) ? -1 : mergesortTree.kthSmallest(i, j, k);
writer.println(k);
// writer.println("------------------------------------------------------");
}
}
}
}
class MergesortTree {
final int n;
final Pair[] a;
List<Pair>[] tree;
public MergesortTree(Pair[] list, int size) {
n = size - 1;
a = list;
tree
= new List[4 * size
+ 1];
constructTree(0, 0, n);
}
public Integer kthSmallest
(int left,
int right,
int k
) { return kthSmallestQuery(0, 0, n, left - 1, right - 1, k);
}
private Integer leftChild
(int node
) { return 2 * node + 1;
}
private Integer rightChild
(int node
) { return 2 * node + 2;
}
private Integer upperBound
(final List
<Pair
> a,
final int key
) {
int low = 0, high = a.size() - 1;
if (key < a.get(low).index) {
return low;
}
if (key >= a.get(high).index) {
return high;
}
while (low <= high) {
int mid = (low + high) / 2;
if (a.get(mid).index <= key) {
if ((mid + 1) < n && a.get(mid + 1).index > key) {
return mid + 1;
}
low = mid + 1;
} else {
high = mid - 1;
}
}
return a.size() - 1;
}
private Integer lowerBound
(final List
<Pair
> a,
final int key
) {
int low = 0, high = a.size() - 1;
if (key <= a.get(low).index) {
return low;
}
if (key >= a.get(high).index) {
return high;
}
while (low <= high) {
int mid = (low + high) / 2;
if (a.get(mid).index >= key) {
if ((mid - 1) >= 0 && a.get(mid - 1).index < key) {
return mid;
}
high = mid - 1;
} else {
low = mid + 1;
}
}
return a.size() - 1;
}
private void constructTree(int node, int low, int high) {
if (low == high) {
tree[node] = new ArrayList<>();
tree[node].add(a[low]);
return;
}
int mid = (low + high) / 2;
int left = leftChild(node);
int right = rightChild(node);
tree[node] = new ArrayList<>();
tree[left] = new ArrayList<>();
tree[right] = new ArrayList<>();
constructTree(left, low, mid);
constructTree(right, mid + 1, high);
int i = 0, j = 0;
int leftEnd = tree[left].size(), rightEnd = tree[right].size();
while (i < leftEnd && j < rightEnd) {
if (tree[left].get(i).index <= tree[right].get(j).index) {
tree[node].add(tree[left].get(i++));
} else {
tree[node].add(tree[right].get(j++));
}
}
while (i < leftEnd) {
tree[node].add(tree[left].get(i++));
}
while (j < rightEnd) {
tree[node].add(tree[right].get(j++));
}
}
private Integer kthSmallestQuery
(int node,
int low,
int high,
int left,
int right,
int k
) {
if (low == high) {
return tree[node].get(0).value;
}
int mid = (low + high) / 2;
int LEFT = leftChild(node);
int RIGHT = rightChild(node);
int greaterThanK = upperBound(tree[LEFT], right);
int smallerThanK = lowerBound(tree[LEFT], left);
int m = greaterThanK - smallerThanK;
// System.out.println((left + 1) + "\t" + (right + 1) + "\t" + (node + 1) + "\t" + (smallerThanK + 1) + "\t" + (greaterThanK + 1) + "\t" + m + "\t" + (k));
if (m >= k) {
return kthSmallestQuery(LEFT, low, mid, left, right, k);
} else {
return kthSmallestQuery(RIGHT, mid + 1, high, left, right, k - m);
}
}
public void showTree() {
for (int i = 0; i < tree.length; i++) {
if (tree[i] != null) {
}
}
}
}
class Pair implements Comparable<Pair> {
final int value, index;
public Pair(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Pair p) {
return this.value - p.value;
}
@Override
return "(" + value + " " + index + ")";
}
}
aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwoKLyoqCiAqIEB1c2VybmFtZTogc3JpbWFuX2NoZXRhbgogKiBAYXV0aG9yOiBDaGV0YW4gUmFpa3dhcgogKiBAZGF0ZTogMjgtMTAtMjAyMAogKi8KY2xhc3MgU29sdXRpb24gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBJT0V4Y2VwdGlvbiB7CgogICAgICAgIHRyeSAoQnVmZmVyZWRSZWFkZXIgcmVhZGVyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKICAgICAgICAgICAgICAgIFByaW50V3JpdGVyIHdyaXRlciA9IG5ldyBQcmludFdyaXRlcihuZXcgT3V0cHV0U3RyZWFtV3JpdGVyKFN5c3RlbS5vdXQpKSkgewoKICAgICAgICAgICAgU3RyaW5nVG9rZW5pemVyIGlucHV0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihyZWFkZXIucmVhZExpbmUoKSk7CgogICAgICAgICAgICBpbnQgbiA9IEludGVnZXIucGFyc2VJbnQoaW5wdXQubmV4dFRva2VuKCkpOwogICAgICAgICAgICBpbnQgbSA9IEludGVnZXIucGFyc2VJbnQoaW5wdXQubmV4dFRva2VuKCkpOwoKICAgICAgICAgICAgaW5wdXQgPSBuZXcgU3RyaW5nVG9rZW5pemVyKHJlYWRlci5yZWFkTGluZSgpKTsKCiAgICAgICAgICAgIFBhaXJbXSBhID0gbmV3IFBhaXJbbl07CgogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICAgICAgaW50IG51bSA9IEludGVnZXIucGFyc2VJbnQoaW5wdXQubmV4dFRva2VuKCkpOwogICAgICAgICAgICAgICAgYVtpXSA9IG5ldyBQYWlyKG51bSwgaSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIEFycmF5cy5zb3J0KGEpOwoKICAgICAgICAgICAgTWVyZ2Vzb3J0VHJlZSBtZXJnZXNvcnRUcmVlID0gbmV3IE1lcmdlc29ydFRyZWUoYSwgbik7CiAgICAgICAgICAgIC8vbWVyZ2Vzb3J0VHJlZS5zaG93VHJlZSgpOwoKICAgICAgICAgICAgd2hpbGUgKG0tLSA+IDApIHsKCiAgICAgICAgICAgICAgICBpbnB1dCA9IG5ldyBTdHJpbmdUb2tlbml6ZXIocmVhZGVyLnJlYWRMaW5lKCkpOwogICAgICAgICAgICAgICAgaW50IGkgPSBJbnRlZ2VyLnBhcnNlSW50KGlucHV0Lm5leHRUb2tlbigpKTsKICAgICAgICAgICAgICAgIGludCBqID0gSW50ZWdlci5wYXJzZUludChpbnB1dC5uZXh0VG9rZW4oKSk7CiAgICAgICAgICAgICAgICBpbnQgayA9IEludGVnZXIucGFyc2VJbnQoaW5wdXQubmV4dFRva2VuKCkpOwoKICAgICAgICAgICAgICAgIGsgPSAoayA+IChqIC0gaSArIDEpKSA/IC0xIDogbWVyZ2Vzb3J0VHJlZS5rdGhTbWFsbGVzdChpLCBqLCBrKTsKICAgICAgICAgICAgICAgIHdyaXRlci5wcmludGxuKGspOwogICAgICAgICAgICAgICAgLy8gd3JpdGVyLnByaW50bG4oIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIpOwoKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKY2xhc3MgTWVyZ2Vzb3J0VHJlZSB7CgogICAgZmluYWwgaW50IG47CiAgICBmaW5hbCBQYWlyW10gYTsKICAgIExpc3Q8UGFpcj5bXSB0cmVlOwoKICAgIHB1YmxpYyBNZXJnZXNvcnRUcmVlKFBhaXJbXSBsaXN0LCBpbnQgc2l6ZSkgewogICAgICAgIG4gPSBzaXplIC0gMTsKICAgICAgICBhID0gbGlzdDsKICAgICAgICB0cmVlID0gbmV3IExpc3RbNCAqIHNpemUgKyAxXTsKCiAgICAgICAgY29uc3RydWN0VHJlZSgwLCAwLCBuKTsKICAgIH0KCiAgICBwdWJsaWMgSW50ZWdlciBrdGhTbWFsbGVzdChpbnQgbGVmdCwgaW50IHJpZ2h0LCBpbnQgaykgewogICAgICAgIHJldHVybiBrdGhTbWFsbGVzdFF1ZXJ5KDAsIDAsIG4sIGxlZnQgLSAxLCByaWdodCAtIDEsIGspOwogICAgfQoKICAgIHByaXZhdGUgSW50ZWdlciBsZWZ0Q2hpbGQoaW50IG5vZGUpIHsKICAgICAgICByZXR1cm4gMiAqIG5vZGUgKyAxOwogICAgfQoKICAgIHByaXZhdGUgSW50ZWdlciByaWdodENoaWxkKGludCBub2RlKSB7CiAgICAgICAgcmV0dXJuIDIgKiBub2RlICsgMjsKICAgIH0KCiAgICBwcml2YXRlIEludGVnZXIgdXBwZXJCb3VuZChmaW5hbCBMaXN0PFBhaXI+IGEsIGZpbmFsIGludCBrZXkpIHsKCiAgICAgICAgaW50IGxvdyA9IDAsIGhpZ2ggPSBhLnNpemUoKSAtIDE7CgogICAgICAgIGlmIChrZXkgPCBhLmdldChsb3cpLmluZGV4KSB7CiAgICAgICAgICAgIHJldHVybiBsb3c7CiAgICAgICAgfQoKICAgICAgICBpZiAoa2V5ID49IGEuZ2V0KGhpZ2gpLmluZGV4KSB7CiAgICAgICAgICAgIHJldHVybiBoaWdoOwogICAgICAgIH0KCiAgICAgICAgd2hpbGUgKGxvdyA8PSBoaWdoKSB7CgogICAgICAgICAgICBpbnQgbWlkID0gKGxvdyArIGhpZ2gpIC8gMjsKCiAgICAgICAgICAgIGlmIChhLmdldChtaWQpLmluZGV4IDw9IGtleSkgewoKICAgICAgICAgICAgICAgIGlmICgobWlkICsgMSkgPCBuICYmIGEuZ2V0KG1pZCArIDEpLmluZGV4ID4ga2V5KSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG1pZCArIDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBsb3cgPSBtaWQgKyAxOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgaGlnaCA9IG1pZCAtIDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHJldHVybiBhLnNpemUoKSAtIDE7CiAgICB9CgogICAgcHJpdmF0ZSBJbnRlZ2VyIGxvd2VyQm91bmQoZmluYWwgTGlzdDxQYWlyPiBhLCBmaW5hbCBpbnQga2V5KSB7CgogICAgICAgIGludCBsb3cgPSAwLCBoaWdoID0gYS5zaXplKCkgLSAxOwoKICAgICAgICBpZiAoa2V5IDw9IGEuZ2V0KGxvdykuaW5kZXgpIHsKICAgICAgICAgICAgcmV0dXJuIGxvdzsKICAgICAgICB9CgogICAgICAgIGlmIChrZXkgPj0gYS5nZXQoaGlnaCkuaW5kZXgpIHsKICAgICAgICAgICAgcmV0dXJuIGhpZ2g7CiAgICAgICAgfQoKICAgICAgICB3aGlsZSAobG93IDw9IGhpZ2gpIHsKCiAgICAgICAgICAgIGludCBtaWQgPSAobG93ICsgaGlnaCkgLyAyOwoKICAgICAgICAgICAgaWYgKGEuZ2V0KG1pZCkuaW5kZXggPj0ga2V5KSB7CgogICAgICAgICAgICAgICAgaWYgKChtaWQgLSAxKSA+PSAwICYmIGEuZ2V0KG1pZCAtIDEpLmluZGV4IDwga2V5KSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG1pZDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGhpZ2ggPSBtaWQgLSAxOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgbG93ID0gbWlkICsgMTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGEuc2l6ZSgpIC0gMTsKICAgIH0KCiAgICBwcml2YXRlIHZvaWQgY29uc3RydWN0VHJlZShpbnQgbm9kZSwgaW50IGxvdywgaW50IGhpZ2gpIHsKCiAgICAgICAgaWYgKGxvdyA9PSBoaWdoKSB7CiAgICAgICAgICAgIHRyZWVbbm9kZV0gPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICAgICAgdHJlZVtub2RlXS5hZGQoYVtsb3ddKTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgaW50IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CiAgICAgICAgaW50IGxlZnQgPSBsZWZ0Q2hpbGQobm9kZSk7CiAgICAgICAgaW50IHJpZ2h0ID0gcmlnaHRDaGlsZChub2RlKTsKCiAgICAgICAgdHJlZVtub2RlXSA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIHRyZWVbbGVmdF0gPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICB0cmVlW3JpZ2h0XSA9IG5ldyBBcnJheUxpc3Q8PigpOwoKICAgICAgICBjb25zdHJ1Y3RUcmVlKGxlZnQsIGxvdywgbWlkKTsKICAgICAgICBjb25zdHJ1Y3RUcmVlKHJpZ2h0LCBtaWQgKyAxLCBoaWdoKTsKCiAgICAgICAgaW50IGkgPSAwLCBqID0gMDsKICAgICAgICBpbnQgbGVmdEVuZCA9IHRyZWVbbGVmdF0uc2l6ZSgpLCByaWdodEVuZCA9IHRyZWVbcmlnaHRdLnNpemUoKTsKCiAgICAgICAgd2hpbGUgKGkgPCBsZWZ0RW5kICYmIGogPCByaWdodEVuZCkgewoKICAgICAgICAgICAgaWYgKHRyZWVbbGVmdF0uZ2V0KGkpLmluZGV4IDw9IHRyZWVbcmlnaHRdLmdldChqKS5pbmRleCkgewogICAgICAgICAgICAgICAgdHJlZVtub2RlXS5hZGQodHJlZVtsZWZ0XS5nZXQoaSsrKSk7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB0cmVlW25vZGVdLmFkZCh0cmVlW3JpZ2h0XS5nZXQoaisrKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHdoaWxlIChpIDwgbGVmdEVuZCkgewogICAgICAgICAgICB0cmVlW25vZGVdLmFkZCh0cmVlW2xlZnRdLmdldChpKyspKTsKICAgICAgICB9CgogICAgICAgIHdoaWxlIChqIDwgcmlnaHRFbmQpIHsKICAgICAgICAgICAgdHJlZVtub2RlXS5hZGQodHJlZVtyaWdodF0uZ2V0KGorKykpOwogICAgICAgIH0KICAgIH0KCiAgICBwcml2YXRlIEludGVnZXIga3RoU21hbGxlc3RRdWVyeShpbnQgbm9kZSwgaW50IGxvdywgaW50IGhpZ2gsIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCBrKSB7CgogICAgICAgIGlmIChsb3cgPT0gaGlnaCkgewogICAgICAgICAgICByZXR1cm4gdHJlZVtub2RlXS5nZXQoMCkudmFsdWU7CiAgICAgICAgfQoKICAgICAgICBpbnQgbWlkID0gKGxvdyArIGhpZ2gpIC8gMjsKICAgICAgICBpbnQgTEVGVCA9IGxlZnRDaGlsZChub2RlKTsKICAgICAgICBpbnQgUklHSFQgPSByaWdodENoaWxkKG5vZGUpOwoKICAgICAgICBpbnQgZ3JlYXRlclRoYW5LID0gdXBwZXJCb3VuZCh0cmVlW0xFRlRdLCByaWdodCk7CiAgICAgICAgaW50IHNtYWxsZXJUaGFuSyA9IGxvd2VyQm91bmQodHJlZVtMRUZUXSwgbGVmdCk7CgogICAgICAgIGludCBtID0gZ3JlYXRlclRoYW5LIC0gc21hbGxlclRoYW5LOwoKICAgICAgICAvLyBTeXN0ZW0ub3V0LnByaW50bG4oKGxlZnQgKyAxKSArICJcdCIgKyAocmlnaHQgKyAxKSArICJcdCIgKyAobm9kZSArIDEpICsgIlx0IiArIChzbWFsbGVyVGhhbksgKyAxKSArICJcdCIgKyAoZ3JlYXRlclRoYW5LICsgMSkgKyAiXHQiICsgbSArICJcdCIgKyAoaykpOwogICAgICAgIGlmIChtID49IGspIHsKICAgICAgICAgICAgcmV0dXJuIGt0aFNtYWxsZXN0UXVlcnkoTEVGVCwgbG93LCBtaWQsIGxlZnQsIHJpZ2h0LCBrKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4ga3RoU21hbGxlc3RRdWVyeShSSUdIVCwgbWlkICsgMSwgaGlnaCwgbGVmdCwgcmlnaHQsIGsgLSBtKTsKICAgICAgICB9CgogICAgfQoKICAgIHB1YmxpYyB2b2lkIHNob3dUcmVlKCkgewoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHRyZWUubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgaWYgKHRyZWVbaV0gIT0gbnVsbCkgewogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHRyZWVbaV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgpjbGFzcyBQYWlyIGltcGxlbWVudHMgQ29tcGFyYWJsZTxQYWlyPiB7CgogICAgZmluYWwgaW50IHZhbHVlLCBpbmRleDsKCiAgICBwdWJsaWMgUGFpcihpbnQgdmFsdWUsIGludCBpbmRleCkgewoKICAgICAgICB0aGlzLnZhbHVlID0gdmFsdWU7CiAgICAgICAgdGhpcy5pbmRleCA9IGluZGV4OwogICAgfQoKICAgIEBPdmVycmlkZQogICAgcHVibGljIGludCBjb21wYXJlVG8oUGFpciBwKSB7CiAgICAgICAgcmV0dXJuIHRoaXMudmFsdWUgLSBwLnZhbHVlOwogICAgfQoKICAgIEBPdmVycmlkZQogICAgcHVibGljIFN0cmluZyB0b1N0cmluZygpIHsKICAgICAgICByZXR1cm4gIigiICsgdmFsdWUgKyAiICIgKyBpbmRleCArICIpIjsKICAgIH0KfQo=