2A2015

#include<stdio.h>

/*
    Złożoność obliczeniowa: O(logn)
    Złożoność pamięciowa: O(1)
*/
/*
    Generalnie korzystamy z tego, że mediana na pewno nie będzie w pierwszym n/2, ani w ostatnim n/2
    No i potem robimi binsearch wykreślając odpowiednią stronę, w której na pewno nie ma mediany
    (Coś analogicznego do mediany sumy)
*/
int MedianaRoznicy(int b[], int a[], int n) {
    int m = (n / 2);
    int beg = m, end = 3 * m;
    while(beg < end) {
        int poz_a = (beg + end) / 2;
        printf("poz_a = %d\n", poz_a);
        int poz_b = poz_a - m;
        if(b[poz_b] <= a[poz_a])
            beg = poz_a + 1;
        else
            end = poz_a;
    }
    return a[beg];
}

int main()
{
    int n; scanf("%d", &n);
    int b[n], a[2*n + 1];
    for(int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    for(int i = 0; i < 2*n + 1; i++)
        scanf("%d", &a[i]);
    printf("%d\n", MedianaRoznicy(b, a, n));
}