1 struct DQ {
 2     priority_queue<int, vector<int>, greater<int> >up;
 3     priority_queue<int>down;
 4     void clear() {
 5         while(!up.empty()) {
 6             up.pop();
 7         }
 8         while(!down.empty()) {
 9             down.pop();
10         }
11         return;
12     }
13     void insert(int a) {
14         if(down.empty()) {
15             down.push(a);
16             return;
17         }
18         if(a > down.top()) {
19             up.push(a);
20         }
21         else {
22             down.push(a);
23         }
24         if(up.size() + 1 < down.size()) {
25             up.push(down.top());
26             down.pop();
27         }
28         else if(up.size() > down.size()) {
29             down.push(up.top());
30             up.pop();
31         }
32         return;
33     }
34     int getmid() {
35         if(up.size() < down.size()) {
36             return down.top();
37         }
38         return (up.top() + down.top()) >> 1;
39     }
40 }dq;