暴力（口胡）
期望得分：未知（待补充）
思路
我们可以直接模拟盒子内的操作，因为每次取的是最值，因此我们可以使用堆维护。每次进行$GET$操作时$pop$出$i - 1$个元素此时的堆顶就是最值，然后再将$i - 1$个元素$ insert $到堆尾$ checkup $。
复杂度分析
设$ ADD $操作$ n $次（堆里最多有$n$个元素），$GET$操作$ m $次。
首先，对于每次$ ADD $操作都需要向堆里$ push $一个元素，需要操作$n$次，复杂度为$O(n\ log\ n)$。
而对于每次$GET$操作，第$i$次操作需要执行$i - 1$次$pop$，$i - 1$次$insert$，与一次$gettop$。其中$gettop$的复杂度为$O(1)$，执行$m$次复杂度为$O(m)$。而$pop$与$insert$最多执行的次数约为$m^2$每次的复杂度为$O(log\ n)$，总复杂度为$O(m^2 \ log\ n)$。
那么很显然代入最大的复杂度是肯定会炸掉的qwq。
对顶堆（正解）
思路
首先对于暴力做法，因为每次都要取最值，所以$O(n \ log\ n)$的建堆是最基础的我们不优先考虑优化，尽量去优化其他的步骤。而很显然我们进行第$i$次$GET$操作时，需要$i - 1$次$pop$与$i - 1$次$insert$ （这操作看起来就很像脱裤子放屁啊喂w），我们需要维护一个集合$S$，在每次$pop$操作前将栈顶元素存在集合，并在$gettop$操作之后将元素从集合中取出并插入堆尾。
很显然，因为我们在执行完第$i$次$GET$操作之后，第$i+1$次我们所要求的是第$i + 1$大的元素。而在我们所维护的集合$S$中肯定是不存在的。那么我们是不是就不用将这些元素插回堆里了呢！！！（啪！）（好疼qwq） 因为我们后面还要执行$ADD$操作，而如果我们所$ADD$的元素$u$比集合里其中的某个元素小，那么这个元素很显然就是有用的w。
那么到底哪些元素是有用的呢qwq？
假设我们集合$S$中所存的为第$i$次$GET$操作时的状态。而我们现在执行$ADD(u)$，如果$u <a$且$a ∈ S$。那么如果我们集合中的元素个数为$n$，且$ 1 ≤ n ≤ 30000$。那么如果$a$为集合中的一个数，那么很显然因为集合$S$中为第$1$~第$i-1$小的数，而如果$u$比这些数当中的某个数还要小的话，那么很显然在下一次求解$GET$的时候$u$肯定会被加入集合$S$中，而因为多了一个比$a$小的数，集合$S$中最大的数从第$i-1$大的数变成了第$i$大的数了。
那么我们可以维护一个集合$S’$，每次$ADD$元素时都将元素插入$S’$，而当$S’$中的元素个数等于$i + 1$的时候，取出最大的元素加入最小堆，每次$GET$取出最小堆堆顶。如上所述，如果我们插入的元素小于集合中的某个元素，那么答案就有可能在集合中最大的元素产生，如果大于集合中的所有元素，那么插入的元素也有可能是答案，而插入的元素又恰好是集合中最大的元素。而对于集合$S’$很显然我们可以使用一个最大堆进行维护。
复杂度分析
设$ ADD $操作$ n $次（堆里最多有$n$个元素），$GET$操作$ m $次。
首先，对于每次$ ADD $操作都需要向堆里$ push $一个元素，需要操作$n$次，复杂度为$O(n\ log\ n)$。
而显然对于每个元素来说最多入堆一次，出堆一次，因此复杂度为$O(n\ log\ n)$
整体复杂度可以控制在$O(n\ log\ n)$。而这个复杂度我们是可以接受的w。
代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int N = 300010;
int a[N],b[N];
int n,m;
priority_queue<int,vector<int> ,greater<int> > minhp;
priority_queue<int> maxhp;
int main(){
scanf("%d%d",&n,&m);
for (int i = 0;i < n; i++){
scanf("%d",&a[i]);
}
for (int i = 0; i < m; i++){
scanf("%d",&b[i]);
}
int cnt = 1,pos = 0;
for (int i = 0; i < n; i++){
maxhp.push(a[i]);
if(maxhp.size() == cnt) minhp.push(maxhp.top()),maxhp.pop();
for (int j = pos; j < m; j++){
if (i + 1 == b[j]){
printf("%d\n",minhp.top());
cnt++;
pos++;
maxhp.push(minhp.top());
minhp.pop();
if (b[j + 1] != b[j]) break;
}
}
}
return 0;
}
