#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct BIT {
    int n = 600000, t[600010];
    void modify(int k, int x) {
        k += 300000;
        for (int i = k; i <= n; i += i & (-i)) {
            t[i] += x;
        }
    }
    int query(int k) {
        k += 300000;
        int ans = 0;
        for (int i = k; i >= 1; i -= i & (-i)) {
            ans += t[i];
        }
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bt;
int n, a[300010], b[300010], s[300010], now[600010];
int check(int mid, int id) {
    for (int i = 1; i <= n; i++) {
        if (a[i] < mid) {
            b[i] = -1;
        } else if (a[i] > mid) {
            b[i] = 1;
        } else {
            b[i] = 0;
        }
    }
    memset(bt.t, 0, sizeof(bt.t));
    bt.modify(0, 1);
    now[300000]++;
    int l = 0, g = 0, e = 0;
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        int tmp = bt.query(b[i]) - now[b[i] + 300000];
        g += tmp;
        e += now[b[i] + 300000];
        l += i - tmp - now[b[i] + 300000];
        bt.modify(b[i], 1);
        now[b[i] + 300000]++;
    }
    now[300000]--;
    for (int i = 1; i <= n; i++) {
        now[b[i] + 300000]--;
    }
    // printf("%d %d : %d %d %d\n", mid, id, l, e, g);
    if (id <= l) return -1;
    if (id > l + e) return 1;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = a[i];
    }
    sort(s + 1, s + n + 1);
    int tot = n * (n + 1) / 2;
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int ck = check(s[mid], (tot + 1) / 2);
        if (ck == 0) {
            ans = mid;
            break;
        }
        if (ck == 1) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", s[ans]);
    return 0;
}#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct BIT {
    int n = 600000, t[600010];
    void modify(int k, int x) {
        k += 300000;
        for (int i = k; i <= n; i += i & (-i)) {
            t[i] += x;
        }
    }
    int query(int k) {
        k += 300000;
        int ans = 0;
        for (int i = k; i >= 1; i -= i & (-i)) {
            ans += t[i];
        }
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bt;
int n, a[300010], b[300010], s[300010], now[600010];
int check(int mid, int id) {
    for (int i = 1; i <= n; i++) {
        if (a[i] < mid) {
            b[i] = -1;
        } else if (a[i] > mid) {
            b[i] = 1;
        } else {
            b[i] = 0;
        }
    }
    memset(bt.t, 0, sizeof(bt.t));
    bt.modify(0, 1);
    now[300000]++;
    int l = 0, g = 0, e = 0;
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        int tmp = bt.query(b[i]) - now[b[i] + 300000];
        g += tmp;
        e += now[b[i] + 300000];
        l += i - tmp - now[b[i] + 300000];
        bt.modify(b[i], 1);
        now[b[i] + 300000]++;
    }
    now[300000]--;
    for (int i = 1; i <= n; i++) {
        now[b[i] + 300000]--;
    }
    // printf("%d %d : %d %d %d\n", mid, id, l, e, g);
    if (id <= l) return -1;
    if (id > l + e) return 1;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = a[i];
    }
    sort(s + 1, s + n + 1);
    int tot = n * (n + 1) / 2;
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int ck = check(s[mid], (tot + 1) / 2);
        if (ck == 0) {
            ans = mid;
            break;
        }
        if (ck == 1) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", s[ans]);
    return 0;
}

answer.code:82:2: error: stray '#' in program
 }#include <cstdio>\x0d
  ^
answer.code:82:3: error: 'include' does not name a type
 }#include <cstdio>\x0d
   ^
answer.code:86:8: error: redefinition of 'struct BIT'
 struct BIT {\x0d
        ^
answer.code:5:8: error: previous definition of 'struct BIT'
 struct BIT {\x0d
        ^
answer.code:105:5: error: invalid type in declaration before ';' token
 } bt;\x0d
     ^
answer.code:105:5: error: conflicting declaration 'int bt'
answer.code:24:3: error: 'bt' has a pr...