K-ci ədəd#3866

K-ci ədəd

1 saniyə

128 meqabayt

Asan

Siz Macrohard şirkətində məlumat strukturları şöbəsində işləyirsiniz. Keçmiş açar daxil etmə məsələsinin uğursuz həllindən sonra sizə massivdəki bir səgment üzrə $k$ -cı statistikayı tez tapmağı təmin edən yeni bir məlumat strukturu hazırlamaq tapşırılıb.

Verilmiş $n$ müxtəlif tam ədəd olan $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n massivinə dair proqramınız çoxlu sorğu $Q (i, j, k)$ Q(i, j, k)-ya cavab verməlidir: “Əgər $a_{i}, a_{i + 1}, \dots, a_{j}$ a_i, a_{i+1}, \dots, a_j səgmenti sıralansa, $k$ -cı ən kiçik element hansı olar?”

Məsələn, $a = (1, 5, 2, 6, 3, 7, 4)$ a = (1, 5, 2, 6, 3, 7, 4) massivinə baxaq. $Q (2, 5, 3)$ Q(2, 5, 3) sorğusunu nəzərdən keçirək. $a_{2}, a_{3}, a_{4}, a_{5}$ a_2, a_3, a_4, a_5 səgmenti $(5, 2, 6, 3)$ (5, 2, 6, 3) olacaq. Bu səgmenti sıralasaq, $(2, 3, 5, 6)$ (2, 3, 5, 6) alınır və üçüncü ən kiçik ədəd $5$ olur. Beləliklə, cavab $5$ olur.

\InputFileBirinci sətir massiv ölçüsü $n$ və sorğuların sayı $m$ ( $1 \leq n \leq 100000$ 1 \le n \le 100\,000, $1 \leq m \leq 5000$ 1 \le m \le 5\,000) — massiv və sorğuların sayı.

İkinci sətir $n$ müxtəlif tam ədədi $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $∣ a_{i} ∣ \leq 1 0^{9}$ |a_i| \le 10^9) ehtiva edir.

Növbəti $m$ sətrin hər birində üç tam ədəd $i$ , $j$ , və $k$ ( $1 \leq i \leq j \leq n$ 1 \le i \le j \le n, $1 \leq k \leq j - i + 1$ 1 \le k \le j-i+1) verilir və bu $Q (i, j, k)$ Q(i, j, k) sorğusunu ifadə edir.

\OutputFileHər bir sorğu üçün cavab verin: sıralanmış $a_{i}, \dots, a_{j}$ a_i, \dots, a_j səgmentində $k$ -cı ən kiçik ədədi çap edin.

Nümunələr

Nümunə 1

Loading

a_{1}, a_{2}, \dots, a_{n}

Q (i, j, k)

a_{i}, a_{i + 1}, \dots, a_{j}

a = (1, 5, 2, 6, 3, 7, 4)

Q (2, 5, 3)

a_{2}, a_{3}, a_{4}, a_{5}

(5, 2, 6, 3)

(2, 3, 5, 6)

1 \leq n \leq 100000

1 \leq m \leq 5000

a_{1}, a_{2}, \dots, a_{n}

∣ a_{i} ∣ \leq 1 0^{9}

1 \leq i \leq j \leq n

1 \leq k \leq j - i + 1

Q (i, j, k)

a_{i}, \dots, a_{j}