[코드업] 3210 - 기억력 테스트 5

주현이의 실력이 늘자 주현이 엄마는 더욱 사악해져 갔다.

이번에도 n개의 숫자를 불러주고, m개의 질문을 한다.

이번에 질문은 두 수 a, b를 이야기하는데, a번째에서 b번째 불렀던 수들 중 가장 큰 수를 묻는다.

예를 들어 2 100 24 99 25 24을 불러주고 3 6이라고 질문하면 3번째와 6번째 사이의 수 중 가장 큰 수인 99를 말해야 한다.

이번에는 없어서 못 파는 "파워레인저 다이노포스 티라노킹"이 걸려있다.

입력

첫 줄에 불러줄 숫자의 개수 n이 입력된다. ( 1 <= n <= 50,000 )

둘째 줄에 n개의 숫자가 공백으로 분리되어 입력된다. (입력 수의 범위 : 1 ~ 40,000)

셋째 줄에 질문의 수 m이 입력된다. ( 1 <= m <= 200,000 )

넷째 줄 부터 m개의 질문이 입력되는데, 시작 수 a, 마지막 수 b가 입력된다. ( 1 <= a <= b <= n )

출력

질문에 대한 답(a와 b사이의 가장 큰 수)을 차례대로 공백으로 분리하여 출력한다.

입력 예시

6
2 100 24 99 25 24
3
1 6
3 4
5 6

출력 예시

100 99 25

---

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N;
vector<pair<int, int>> query;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	int num;
	for(int i = 0; i < N; i++){
		cin >> num;
		query.push_back({ num , i + 1 });
	}

	sort(query.rbegin(), query.rend());

	int M;
	cin >> M;

	int a, b;
	for(int i = 0; i < M; i++){
		cin >> a >> b;
		for(int j = 0; j < N; j++){
			if(query[j].second >= a && query[j].second <= b){
				cout << query[j].first << " ";
				break;
			}
		}
	}

	return 0;
}