1770: 【入门】找第k小的数

内存限制:16 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:1 解决:1

题目描述

给出一个长度为N的序列A1,A2,A3,...,AN,其中每项都是小于10^5的自然数。
现在有M个询问,每个询问都是Ai...Aj中第k小的数等于多少。

输入

第一行两个正整数N,M。
第二行N个数,表示序列A1,A2,...,AN。
紧着的M行,每行三个正整数i,j,k(k≤j-i+1),表示
询问Ai...Aj中第k小的数等于多少。

输出

共输出M行,第i行输出第i个询问的答案。

样例输入 复制

4 3
4 1 2 3
1 3 1
2 4 3
1 4 4

样例输出 复制

1
3
4

来源/分类