## Editorial for Double Queue

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
maxn=1000000;
var h,g,p,q,a,b:array[0..maxn] of longint;
n,m,i,x,y,z:longint;

procedure updatemin(x,y:longint);
var cha,con:longint;
begin
if q[x]=0 then
begin
inc(m); con:=m;
end
else con:=q[x];
cha:=con shr 1;
while (cha>0) and (y<b[cha]) do
begin
g[con]:=g[cha];
b[con]:=b[cha];
q[g[con]]:=con;
con:=cha;
cha:=con shr 1;
end;
g[con]:=x; q[x]:=con; b[con]:=y;
end;

procedure updatemax(x,y:longint);
var cha,con:longint;
begin
if p[x]=0 then
begin
inc(n); con:=n;
end
else con:=p[x];
cha:=con shr 1;
while (cha>0) and (y>a[cha]) do
begin
h[con]:=h[cha];
a[con]:=a[cha];
p[h[con]]:=con;
con:=cha;
cha:=con shr 1;
end;
h[con]:=x; p[x]:=con; a[con]:=y;
end;

procedure editmin(z:longint);
var cha,con,x,y:longint;
begin
x:=g[m]; y:=b[m]; b[m]:=0; g[m]:=0; dec(m);
if z>m then exit;
cha:=z; con:=z shl 1;
while con<=m do
begin
if (con<m) and (b[con+1]<b[con]) then inc(con);
if y<=b[con] then break;
g[cha]:=g[con];
b[cha]:=b[con];
q[g[cha]]:=cha;
cha:=con;
con:=cha shl 1;
end;
g[cha]:=x; q[x]:=cha; b[cha]:=y;
updatemin(x,y);
end;

procedure editmax(z:longint);
var cha,con,x,y:longint;
begin
x:=h[n]; y:=a[n]; a[n]:=0; h[n]:=0; dec(n);
if z>n then exit;
cha:=z; con:=z shl 1;
while con<=n do
begin
if (con<n) and (a[con+1]>a[con]) then inc(con);
if y>=a[con] then break;
h[cha]:=h[con];
a[cha]:=a[con];
p[h[cha]]:=cha;
cha:=con;
con:=cha shl 1;
end;
h[cha]:=x; p[x]:=cha; a[cha]:=y;
updatemax(x,y);
end;

begin
assign(input,fi); reset(input);
m:=0; n:=0;
while true do
begin
if z=0 then break;
if z=1 then
begin
updatemin(x,y);
updatemax(x,y);
end
else
begin
if z=2 then
begin
if n=0 then
begin
writeln(0); continue;
end;
x:=h[1];
end
else
begin
if m=0 then
begin
writeln(0); continue;
end;
x:=g[1];
end;
writeln(x);
editmin(q[x]);
q[x]:=0;
editmax(p[x]);
p[x]:=0;
end;
end;
close(input);
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<set>
using namespace std;

typedef pair<int, int> ii;
set<ii> memo;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
for(int ctrl; scanf("%d",&ctrl) != EOF && ctrl != 0;) {
if(ctrl == 1) {
int k, p; scanf("%d%d",&k,&p);
memo.insert(ii(p, k));
} else if(memo.empty()) printf("0\n");
else if(ctrl == 2) {
printf("%d\n", memo.rbegin()->second);
set<ii>::iterator it = memo.end();
memo.erase(--it);
} else {
printf("%d\n", memo.begin()->second);
memo.erase(memo.begin());
}
}
}


#### Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int maxK = 1000006;
using namespace std;
priority_queue<iii> heap_max;
priority_queue<iii, vector<iii>, greater<iii> > heap_min;
map<ii, int> M;
int cnt[maxK];

int main()
{
int type, k, p; iii e;
scanf("%d", &type);
while (type != 0) {
if (type == 1) {
scanf("%d %d\n", &k, &p);
cnt[k]++;
heap_min.push(iii(p, ii(k, cnt[k])));
heap_max.push(iii(p, ii(k, cnt[k])));
}
if (type == 2) {
if (heap_max.size() == 0) {printf("0\n");}
else {
do {
e = heap_max.top(); heap_max.pop();
k = e.Y.X;
} while (heap_max.size() && M.count(ii(k, e.Y.Y)) != 0);
if (M.count(ii(k, e.Y.Y)) != 0)
{printf("0\n");}
else {
M.insert(pair<ii, int> (ii(k, e.Y.Y), 1));
printf("%d\n", k);
}
}
}
if (type == 3) {
if (heap_min.size() == 0) {printf("0\n");}
else {
do {
e = heap_min.top(); heap_min.pop();
k = e.Y.X;
} while (heap_min.size() && M.count(ii(k, e.Y.Y)) != 0);
if (M.count(ii(k, e.Y.Y)) != 0)
{printf("0\n");}
else {
M.insert(pair<ii, int> (ii(k, e.Y.Y), 1));
printf("%d\n", k);
}
}
}
scanf("%d", &type);
}
return 0;
}


#### Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+} {$Mode objFPC}
const
FINP='';
FOUT='';
MAXN=1000001;
oo=1000000000;
procedure swap(var a,b:longint);
var temp:longint;
begin temp:=a; a:=b; b:=temp; end;
type
heap=object
hmin,hmax,inmin,inmax,vmin,vmax:array[1..MAXN] of longint;
hminsize,hmaxsize:longint;
procedure downMax(i:longint);
procedure downMin(i:longint);
procedure upMax(i:longint);
procedure upMin(i:longint);
procedure push(u,k:longint);
procedure popMax(var u,k:longint);
procedure popMin(var u,k:longint);
end;
procedure heap.downMax(i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hmaxsize) do
begin
if (j<hmaxsize) and (hmax[j+1]>hmax[j]) then inc(j);
if (hmax[j]>hmax[i]) then
begin
swap(inmax[inmin[i]],inmax[inmin[j]]);
swap(inmin[i],inmin[j]);
swap(hmax[i],hmax[j]);
swap(vmax[i],vmax[j]);
end;
i:=j; j:=i<<1;
end;
end;
procedure heap.downMin(i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hminsize) do
begin
if (j<hminsize) and (hmin[j+1]<hmin[j]) then inc(j);
if (hmin[j]<hmin[i]) then
begin
swap(inmin[inmax[i]],inmin[inmax[j]]);
swap(inmax[i],inmax[j]);
swap(hmin[i],hmin[j]);
swap(vmin[i],vmin[j]);
end;
i:=j; j:=i<<1;
end;
end;
procedure heap.upMax(i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (hmax[i]>hmax[j]) do
begin
swap(inmax[inmin[i]],inmax[inmin[j]]);
swap(inmin[i],inmin[j]);
swap(hmax[i],hmax[j]);
swap(vmax[i],vmax[j]);
i:=j; j:=i>>1;
end;
end;
procedure heap.upMin(i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (hmin[i]<hmin[j]) do
begin
swap(inmin[inmax[i]],inmin[inmax[j]]);
swap(inmax[i],inmax[j]);
swap(hmin[i],hmin[j]);
swap(vmin[i],vmin[j]);
i:=j; j:=i>>1;
end;
end;
procedure heap.push(u,k:longint);
begin
inc(hmaxsize); hmax[hmaxsize]:=u; vmax[hmaxsize]:=k;
inc(hminsize); hmin[hminsize]:=u; vmin[hminsize]:=k;
inmax[hminsize]:=hmaxsize; inmin[hmaxsize]:=hminsize;
upMax(hmaxsize); upMin(hminsize);
end;
procedure heap.popMax(var u,k:longint);
var
v:longint;
begin
u:=hmax[1]; k:=vmax[1];
v:=inmin[1]; hmin[v]:=-maxlongint; upMin(v);
swap(hmax[1],hmax[hmaxsize]);
swap(vmax[1],vmax[hmaxsize]);
swap(inmin[1],inmin[hmaxsize]);
inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize;
swap(hmin[1],hmin[hminsize]);
swap(vmin[1],vmin[hminsize]);
swap(inmax[1],inmax[hmaxsize]);
inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize;
dec(hminsize); downMin(1);
dec(hmaxsize); downMax(1);
end;
procedure heap.popMin(var u,k:longint);
var
v:longint;
begin
u:=hmin[1]; k:=vmin[1];
v:=inmax[1]; hmax[v]:=maxlongint; upMax(v);
swap(hmax[1],hmax[hmaxsize]);
swap(vmax[1],vmax[hmaxsize]);
swap(inmin[1],inmin[hmaxsize]);
inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize;
swap(hmin[1],hmin[hminsize]);
swap(vmin[1],vmin[hminsize]);
swap(inmax[1],inmax[hminsize]);
inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize;
dec(hminsize); downMin(1);
dec(hmaxsize); downMax(1);
end;

var
a:heap;
u,k,request:longint;
begin
//  assign(input,'input.txt'); reset(input);
//  assign(output,'output.txt'); rewrite(output);
while request>0 do
begin
case request of
1: begin
a.push(u,k);
end;
2: if a.hmaxsize=0 then writeln(0)
else
begin
a.popMax(u,k);
writeln(k);
end;
3: if a.hminsize=0 then writeln(0)
else
begin
a.popMin(u,k);
writeln(k);
end;
end;
end;
//  close(input); close(output);
end.


#### Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, 0, 0, -1, +1};
const int dc[] = {0, -1, +1, 0, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = ld(1e-12);
const ll mod = 1000000000;
typedef pair<int, int> II;

#define maxn 100005

using namespace std;

int id;
set<II> S;
set<II>::iterator it;
int k, n;

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
while(scanf("%d", &id) > 0 && id > 0){
if(id == 1){
scanf("%d %d", &k, &n);
S.insert(mp(n, k));
}
else{
if(!sz(S))  printf("0\n");
else if(id == 2){
it = S.end();
it--;
printf("%d\n", (*it).se);
S.erase(it);
}
else{
it = S.begin();
printf("%d\n", (*it).se);
S.erase(it);
}
}
}
}


#### Code mẫu của ll931110

#include <iostream>
#include <set>
#include <iterator>
#include <utility>
using namespace std;

set< pair<int,int> > s;

int main()
{
//    freopen("mn.in","r",stdin);
//    freopen("mn.ou","w",stdout);

int q;
pair<int,int> u;
int k1,k2;

do
{
//        cout << s.size() << endl;
scanf("%d", &q);
if (q == 0) break;
if (q == 1)
{
scanf("%d%d", &k2, &k1);
u = make_pair(k1,k2);
s.insert(u);
}
else
{
if (s.empty()) printf("%d\n", 0);
else
{
if (q == 2) u = *--s.end(); else u = *s.begin();
printf("%d\n", u.second);
s.erase(u);
};
};
}
while (q != 0);
};