#include <bits/stdc++.h>
using namespace std;

class Random
{
public:
    //随机化分割
    int randomized_partition(vector<int> &a, int p, int r);
    int randomized_select(vector<int> &a, int p, int r, int i);
};

//下标为[p, r]之间的元素
int Random::randomized_partition(vector<int> &a, int p, int r)
{
    int q = rand() % (r - p + 1) + p; //就是说先随机选一个--在p-r之间选一个包含p r
    int temp = a[q];
    a[q] = a[r];
    a[r] = temp;
    int i = p - 1;
    for (int j = p; j < r; j++)
    {
        if (a[j] < a[r])
        {
            i = i + 1;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp = a[i + 1];
    a[i + 1] = a[r];
    a[r] = temp;
    return i + 1;
}

//迭代版本
int Random::randomized_select(vector<int> &a, int p, int r, int i)
{
    if (p == r)
        return a[p];
    int q;
    q = randomized_partition(a, p, r);//用来划分的那个数的下标
    int k;
    k = q - p + 1;//可以得到用来划分的那个数是第几大的
    if (i == k)
        return a[q];
    else if (i < k)
        return randomized_select(a, p, q - 1, i);
    else
        return randomized_select(a, q + 1, r, i - k);
}

int main()
{
    Random c;
    vector<int> a;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        a.push_back(b);
        //cout<<a[i]<<endl;
    }
    cout << c.randomized_select(a, 0, n - 1, n / 2);
}

#include<bits/stdc++.h>
using namespace std;

class middle
{
    public:
    void insert_sort(int array[], int left, int a);
    int find_middle(int array[], int left, int right);
    int find_index(int array[], int left, int right, int median);
    int Select(int array[], int left, int right, int k);

    private:
    int middle_array[900000];//用一个中位数数组来储存产生的中位数

};

void middle::insert_sort(int array[], int left, int a)//left是数组开始的下标，a代表了数组还有几个元素
{
    for (int j = left; j < left + a; j++)
    {
        int key = array[j];
        int i = j - 1;
        while (i > left && array[i] > key)
        {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = key;
    }
}

int middle::find_middle(int array[], int left, int right)
{
    if (left == right)
        return array[left];

    int index;
    for (index = left; index < right - 5; index += 5)
    {
        insert_sort(array, index, 4);
        int num = index - left;
        middle_array[num / 5] = array[index + 2];
    }

    // 处理剩余元素
    int remain = right - index + 1;
    if (remain > 0)
    {
        insert_sort(array, index, remain - 1);
        int num = index - left;
        middle_array[num / 5] = array[index + remain / 2];
    }

    //得到新数组的下标
    int new_array = (right - left) / 5 - 1;
    if ((right - left) % 5 != 0)
        new_array++;

    // 根据剩余条件来看是否递归
    if (new_array == 0)
        return middle_array[0];
    else
        return find_middle(middle_array, 0, new_array);
}

// 寻找中位数的所在位置
int middle::find_index(int array[], int left, int right, int median)
{
    for (int i = left; i <= right; i++)
    {
        if (array[i] == median)
            return i;
    }
    return -1;
}

int middle::Select(int array[], int left, int right, int k)
{
    // 找到所有数的中位数
    int median = find_middle(array, left, right);
    // 将中位数的中位数与最右元素交换
    int index = find_index(array, left, right, median);
    swap(array[index], array[right]);
    //partition
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (array[j] < array[right])
        {
            i = i + 1;
            swap(array[i], array[j]);
        }
    }
    swap(array[i + 1], array[right]);
    //划分之后寻找
    i = i + 1;
    int m = i - left + 1;
    if (m == k)
        return array[i];
    else if (m > k)
        return Select(array, left, i - 1, k);
    else
        return Select(array, i + 1, right, k - m);
}

int main()
{
    middle c;
    int n;
    cin>>n;
    int array[n];
    for(int i =0;i<n;i++)
    {
        cin>>array[i];
    }
    cout << c.Select(array, 0, n- 1, n/2 )<< endl;
    return 0;
}