Description

給定一個長度為?NN?的非負整數序列?AA，對于前奇數項求中位數。

Input

第一行一個正整數?NN。

第二行?NN?個正整數?A1…NA1…N?。

Output

共??N+12??2N+1???行，第?ii?行為?A1…2i?1A1…2i?1??的中位數。

Sample 1

7
1 3 5 7 9 11 6

1
3
5
6

Sample 2

7
3 1 5 9 8 7 6

3
3
5
6

Hint

對于?20%20%?的數據，N≤100N≤100；

對于?40%40%?的數據，N≤3000N≤3000；

對于?100%100%?的數據，1≤N≤1000001≤N≤100000，0≤Ai≤1090≤Ai?≤109。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n;
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}vector<int> m;for (int i = 1; i <= n; i ++) {if (i == 1) {m.insert(m.begin(), a[i]);}else {int x = 0, y = m.size();while (x < y) {int mid = (x + y) / 2;if (m[mid] > a[i]) {y = mid;}else {x = mid + 1;}}m.insert(m.begin() + x, a[i]);}if (i % 2 == 1) {cout << m[m.size() / 2] << endl;}}return 0;
}