#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAXN 100005
#define MIN_VAL -1000000000
#define MAX_VAL 1000000000

// Max-heap for lower half
int maxHeap[MAXN], maxSize = 0;
// Min-heap for upper half
int minHeap[MAXN], minSize = 0;

void swap(int *a, int *b) {
    int tmp = *a; *a = *b; *b = tmp;
}

void maxHeapPush(int val) {
    maxHeap[++maxSize] = val;
    int i = maxSize;
    while (i > 1 && maxHeap[i] > maxHeap[i/2]) {
        swap(&maxHeap[i], &maxHeap[i/2]);
        i /= 2;
    }
}

int maxHeapPop() {
    int top = maxHeap[1];
    maxHeap[1] = maxHeap[maxSize--];
    int i = 1;
    while (2*i <= maxSize) {
        int j = 2*i;
        if (j+1 <= maxSize && maxHeap[j+1] > maxHeap[j]) j++;
        if (maxHeap[i] >= maxHeap[j]) break;
        swap(&maxHeap[i], &maxHeap[j]);
        i = j;
    }
    return top;
}

void minHeapPush(int val) {
    minHeap[++minSize] = val;
    int i = minSize;
    while (i > 1 && minHeap[i] < minHeap[i/2]) {
        swap(&minHeap[i], &minHeap[i/2]);
        i /= 2;
    }
}

int minHeapPop() {
    int top = minHeap[1];
    minHeap[1] = minHeap[minSize--];
    int i = 1;
    while (2*i <= minSize) {
        int j = 2*i;
        if (j+1 <= minSize && minHeap[j+1] < minHeap[j]) j++;
        if (minHeap[i] <= minHeap[j]) break;
        swap(&minHeap[i], &minHeap[j]);
        i = j;
    }
    return top;
}

void balanceHeaps() {
    if (maxSize > minSize + 1) {
        minHeapPush(maxHeapPop());
    } else if (minSize > maxSize) {
        maxHeapPush(minHeapPop());
    }
}

void printMedian() {
    if (maxSize == minSize) {
        double median = (maxHeap[1] + minHeap[1]) / 2.0;
        printf("%.1f\n", median);
    } else {
        printf("%.1f\n", (double)maxHeap[1]);
    }
}

int isValid(char *s, int *val) {
    char *endptr;
    long num = strtol(s, &endptr, 10);
    if (*endptr != '\0') return 0;
    if (num < MIN_VAL || num > MAX_VAL) return 0;
    *val = (int)num;
    return 1;
}

int main() {
    int N;