이 문제를 처음 보았을때 인덱스를 통한 정렬을 생각을 하였는데 시간초를 계산해볼때 10만개의 배열에서 

최악의 경우 계속 마지막 것만 물어보게 된다면 10만 *5000해서 5억정도의 시간이 걸릴 것 같아서 안되겠구나 하고

고민을 해보다 정 안되겠어서 다른 분들의 코드를 읽어보았는데 대부분 이 방식으로 푸신것 같습니다.

제 생각에서 어디가 잘못된 것이 있나요 ?... 아니면 테스트 케이스에서 마지막 것만 찾는 케이스가 없어서 그런건가요?.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 4000005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

typedef struct st
{
    int num;
    int idx;
}str1;

bool cmp(str1 a, str1 b) {
    return a.num < b.num;
}

int n, k, i, j, cnt = 0, st, fi, target;
str1 map[5000005];

int main()
{
    
    scanf("%d %d", &n, &k);
    
    for (i = 0; i < n; i++)
    {
        scanf("%d", &map[i].num);
        map[i].idx = i+1;
    }
    
    sort(map, map+n, cmp);
    
    for (i = 0; i < k; i++)
    {
        scanf("%d %d %d", &st, &fi, &target);
        
        for (j = 0; j < n; j++)
        {
            if (st <= map[j].idx && map[j].idx <= fi)
                cnt++;
            
            if(cnt == target)
            {
                printf("%d\n", map[j].num);
                break;
            }
            
        }
        cnt = 0;
        
    }
}