Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n=int(raw_input())
    a=map(int,raw_input().split())
    now=a
    while 1:
        l=len(now)
        if l==1:
            print(now[0])
            break
        if max(now[0:l/2])<=now[l/2]<=min(now[l/2+1:]):
            print(now[l/2])
            break
        if now[l/2-1]==now[l/2] or now[l/2]==now[l/2+1]:
            print(now[l/2])
            break
        if now[l/2-1]<now[l/2]<now[l/2+1]:
            if now[l/2-2]>=now[l/2]:
                print(now[l/2])
                break
            if now[l/2+2]<=now[l/2]:
                print(now[l/2])
                break
        if now[l/2+1]<now<now[l/2-1]:
            if now[l/2+2]>=now[n/l]:
                print(now[l/2])
                break
            if now[l/2-2]<=now[l/2]:
                print(now[l/2])
                break
        else:
            nx=[]
            for i in xrange(l-2):
                tmp=[]
                tmp.append(now[i])
                tmp.append(now[i+1])
                tmp.append(now[i+2])
                tmp.sort()
                nx.append(tmp[1])
            now=nx

main()

Fixed submission:
def check(m):
    tmpa = [-1] * 2 * n
    for i in xrange(2 * n - 1):
        if a[i] < m:
            tmpa[i] = 0
        else:
            tmpa[i] = 1

    idx = n -1
    while idx < 2 * n - 1:
        idx += 1
        if tmpa[idx - 1] == tmpa[idx]:
            rr = tmpa[idx]
            ridx = idx - 1
            break
    else:
        rr = -1
        ridx = 2 * n - 1

    idx = n - 1
    while idx > 0:
        idx -= 1
        if tmpa[idx + 1] == tmpa[idx]:
            ll = tmpa[idx]
            lidx = idx + 1
            break
    else:
        ll = -1
        lidx = -1

    if rr == ll == -1:
        if n % 2 == 0:
            if tmpa[n - 1] == 1:
                return False
            else:
                return True
        else:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
    elif ridx - (n - 1) == (n - 1) - lidx:
        if rr != ll:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
        else:
            if rr==1:
                return True
            else:
                return False
    elif ridx - (n - 1) > (n - 1) -lidx:
        if ll == 1:
            return True
        else:
            return False
    else:
        if rr == 1:
            return True
        else:
            return False

n = int(raw_input())
a = map(int,raw_input().split())
l = 1
r = 2 * n
while r - l > 1:
    m = (r + l)/2
    if check(m):
        l = m
    else:
        r = m
print(l)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(raw_input())
a=map(int,raw_input().split())
now=a
while 1:
    l=len(now)
    if l==1:
        print(now[0])
        break
    if now[l/2-1]==now[l/2] or now[l/2]==now[l/2+1]:
        print(now[l/2])
        break
    if now[l/2-1]<now[l/2]<now[l/2+1]:
        if now[l/2-2]>=now[l/2]:
            print(now[l/2])
            break
        if now[l/2+2]<=now[l/2]:
            print(now[l/2])
            break
    if now[l/2+1]<now<now[l/2-1]:
        if now[l/2+2]>=now[n/l]:
            print(now[l/2])
            break
        if now[l/2-2]<=now[l/2]:
            print(now[l/2])
            break
    else:
        nx=[]
        for i in xrange(l-2):
            tmp=[]
            tmp.append(now[i])
            tmp.append(now[i+1])
            tmp.append(now[i+2])
            tmp.sort()
            nx.append(tmp[1])
        now=nx


Fixed submission:
def check(m):
    tmpa = [-1] * 2 * n
    for i in xrange(2 * n - 1):
        if a[i] < m:
            tmpa[i] = 0
        else:
            tmpa[i] = 1

    idx = n -1
    while idx < 2 * n - 1:
        idx += 1
        if tmpa[idx - 1] == tmpa[idx]:
            rr = tmpa[idx]
            ridx = idx - 1
            break
    else:
        rr = -1
        ridx = 2 * n - 1

    idx = n - 1
    while idx > 0:
        idx -= 1
        if tmpa[idx + 1] == tmpa[idx]:
            ll = tmpa[idx]
            lidx = idx + 1
            break
    else:
        ll = -1
        lidx = -1

    if rr == ll == -1:
        if n % 2 == 0:
            if tmpa[n - 1] == 1:
                return False
            else:
                return True
        else:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
    elif ridx - (n - 1) == (n - 1) - lidx:
        if rr != ll:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
        else:
            if rr==1:
                return True
            else:
                return False
    elif ridx - (n - 1) > (n - 1) -lidx:
        if ll == 1:
            return True
        else:
            return False
    else:
        if rr == 1:
            return True
        else:
            return False

n = int(raw_input())
a = map(int,raw_input().split())
l = 1
r = 2 * n
while r - l > 1:
    m = (r + l)/2
    if check(m):
        l = m
    else:
        r = m
print(l)