K-ci ədəd
MakroHard şirkətində məlumat strukturları şöbəsində çalışırsınız. Əvvəlki açar daxil etmə məsələsinin uğursuz həllindən sonra, sizdən verilmiş aralıqda k-cı sıravi statistikası tez tapmağa imkan verən yeni bir məlumat strukturu hazırlamağınızı xahiş etdilər.
a[1...n] müxtəlif tam ədədlərdən ibarət bir massiv verilir. Sizdən Q(i, j, k) tipli sorğulara cavab verməyiniz tələb olunur: "Əgər bu aralıqdakı bütün ədədləri əvvəlcə sıralasaq, a[i...j] aralığında k-cı ədədi tapın".
Məsələn, a = (1, 5, 2, 6, 3, 7, 4) massivini nəzərdən keçirək. Q(2, 5, 3) sorğusunu götürək. a[2...5] aralığı (5, 2, 6, 3) olacaq. Ədədləri sıraladıqda, (2, 3, 5, 6) alırıq. Üçüncü element 5 olacaq. Beləliklə, sorğunun cavabı 5 olacaq.
Giriş məlumatları
Birinci sətir massiv ölçüsü n və sorğuların sayı m-i (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000) ehtiva edir.
İkinci sətir n müxtəlif tam ədədləri ehtiva edir, hansılar ki, mütləq dəyəri 10^9-u keçmir - bu ədədlər sorğuların veriləcəyi massivdir.
Sonrakı m sətir sorğuları ehtiva edir, hər biri üç ədəddən ibarətdir: i, j və k (0 ≤ i ≤ j ≤ n, 0 ≤ k ≤ j - i + 1) və Q(i, j, k) sorğusunu təmsil edir.
Çıxış məlumatları
Hər bir sorğu üçün sıralanmış a[i...j] aralığında k-cı ədədi çıxarın.