48 lines
1.2 KiB
C++
48 lines
1.2 KiB
C++
#include <cstdio>
|
|
#include <iostream>
|
|
using namespace std;
|
|
inline int maxs(int yi, int er)
|
|
{
|
|
return yi > er ? yi : er;
|
|
}
|
|
int main()
|
|
{
|
|
int n, m, a[100001] = { 0 };
|
|
scanf("%d", &n);
|
|
for (int i = 1; i <= n; i++) {
|
|
scanf("%d", &a[i]);
|
|
}
|
|
int num[100001] = { 0 }, id[100001] = { 0 };
|
|
int tou = 0, wei = 0;
|
|
scanf("%d", &m);
|
|
for (int i = 1; i <= m; i++) {
|
|
int x, y;
|
|
scanf("%d%d", &x, &y);
|
|
if (id[wei] > x) {
|
|
while (tou < wei && id[tou] < x) {
|
|
tou++;
|
|
}
|
|
for (int j = id[wei] + 1; j <= y; j++) {
|
|
while (tou <= wei && num[wei] < a[j]) {
|
|
wei--;
|
|
}
|
|
wei++;
|
|
num[wei] = a[j];
|
|
id[wei] = j;
|
|
}
|
|
} else {
|
|
tou=wei=x;
|
|
tou++;
|
|
for (int j = x; j <= y; j++) {
|
|
while (tou <= wei && num[wei] < a[j]) {
|
|
wei--;
|
|
}
|
|
wei++;
|
|
num[wei] = a[j];
|
|
id[wei] = j;
|
|
}
|
|
}
|
|
printf("%d\n", id[tou]);
|
|
}
|
|
}
|