1A2018

/*
    Złożoność czasowa: O(n*log(z))
    Złożoność pamięciowa: O(1)
*/

#include <stdio.h>
/*
    Liczy ile jest i, j takich, że A[i] + B[j] <= t
    Złożoność O(n), bo przechodzimy obie tablice jednocześnie
*/
int mniejszesumy(int A[], int B[], int t, int n)
{
    int b = n - 1;
    int mniejsze = 0;
    for (int a = 0; a < n; a++) {
        while (b >= 0 && A[a] + B[b] > t)
            b--;
        mniejsze += (b + 1);
    }
    return mniejsze;
}
/*
    Binsearchuje po wszystkich możliwych sumach od A[0]+B[0] do A[n-1]+B[n-1] i szuka takiej sumy S, że mniejszesumy(s) > n^2/2
    Złożoność czasowa: O(n*log(z)), bo używamy binsearcha w tablicy o wielkości z, ale przy każdym przeszukaniu używamy mniejszesumy o złożoności O(n)
*/
int mediana(int A[], int B[], int n)
{
    int l = A[0] + B[0];
    int r = A[n - 1] + B[n - 1];

    while (l != r) {
        int mid = (l + r) / 2;
        if (mniejszesumy(A, B, mid, n) >= ((n * n) / 2))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int A[n];
    int B[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &B[i]);

    printf("%d\n", mediana(A, B, n));
    return 0;
}