K-ci ədəd (Asan)
MakroHard şirkətində məlumat strukturları şöbəsində çalışırsınız. Əvvəlki açar yerləşdirmə məsələsinin uğursuz həllindən sonra, sizdən verilmiş aralıqda k-cı sıralı statistik məlumatı tez bir zamanda 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 verilmiş aralıqdakı bütün ədədləri əvvəlcədən sıraya düzsək, 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ıraya düzdükdə, (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ü n və sorğuların sayını m (1 ≤ n, m ≤ 100) ehtiva edir.
İkinci sətir, sorğuların veriləcəyi ədədlər massivi olan n müxtəlif tam ədədləri ehtiva edir, bu ədədlərin mütləq dəyəri 10^9-dan çox deyil.
Sonrakı m sətir hər biri üç ədəddən ibarət olan sorğuları ehtiva edir: 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 a[i...j] aralığında sıraya düzülmüş k-cı ədədi çıxarın.