Problem:
 Score : 1300 points    Problem Statement We have a pyramid with N steps, built with blocks.
The steps are numbered 1 through N from top to bottom.
For each 1≤i≤N , step i consists of 2i-1 blocks aligned horizontally.
The pyramid is built so that the blocks at the centers of the steps are aligned vertically.    A pyramid with N=4 steps   Snuke wrote a permutation of ( 1 , 2 , ... , 2N-1 ) into the blocks of step N .
Then, he wrote integers into all remaining blocks, under the following rule:   The integer written into a block b must be equal to the median of the three integers written into the three blocks directly under b , or to the lower left or lower right of b .     Writing integers into the blocks   Afterwards, he erased all integers written into the blocks.
Now, he only remembers that the permutation written into the blocks of step N was ( a_1 , a_2 , ... , a_{2N-1} ).  Find the integer written into the block of step 1 .      Constraints  2≤N≤10^5  ( a_1 , a_2 , ... , a_{2N-1} ) is a permutation of ( 1 , 2 , ... , 2N-1 ).         Input The input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_{2N-1}       Output Print the integer written into the block of step 1 .        Sample Input 1 4
1 6 3 7 4 5 2      Sample Output 1 4  This case corresponds to the figure in the problem statement.       Sample Input 2 2
1 2 3      Sample Output 2 2

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
def cond(n):
    L=(0,-1)
    for i in range(1,N):
        if a[i]>=n and a[i-1]>=n:
            L=(i,1)
        elif a[i]<n and a[i-1]<n:
            L=(i,0)

    R=(2*N-1,-1)
    for i in range(2*N-3,N-2,-1):
        if a[i]>=n and a[i+1]>=n:
            R=(i,1)
        elif a[i]<n and a[i+1]<n:
            R=(i,0)

    if L[1]==-1 and R[1]==-1:
        return a[0]>=n
    elif L[1]==-1:
        return R[1]==1
    elif R[1]==-1:
        return L[1]==1
    elif L[1]==R[1]:
        return R[1]==1
    else:
        if L[1]==0:
            return N-1-L[0]>R[0]-(N-1)
        else:
            return N-1-L[0]<R[0]-(N-1)


start=1
end=2*N-1
while end-start>1:
    test=(end+start)//2
    if cond(test):
        start=test
    else:
        end=test
if cond(end):
    print(end)
else:
    print(start)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
l, r = 1, n * 2
while r - l > 1:
    m = (l + r) // 2
    li = [0] * (2 * n - 1)
    for i in range(2 * n - 1):
        if a[i] >= m:
            li[i] = 1
    t = li[n - 1]
    for i in range(n - 1):
        if ((t + li[n + i] + i) & 1 == 0):
            if li[n + i] & 1:
                l = m
            else:
                r = m
            break
        if((t + li[n - i - 2] + i) & 1 == 0):
            if li[n - i - 2] & 1:
                l = m
            else:
                r = m
            break
    else:
        if (n + t) & 1:
            r = m
        else:
            l = m
print(l)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def check(mid):
    if a[n - 1] >= mid and (a[n - 2] >= mid or a[n] >= mid):
        return True
    elif a[n - 1] < mid and (a[n - 2] < mid or a[n] < mid):
        return False
    
    l = n - 1
    while l > 0:
        if (a[l] < mid) ^ (a[l - 1] < mid):
            l -= 1
        else:
            break
    
    r = n - 1
    while r < n * 2 - 2:
        if (a[r] < mid) ^ (a[r + 1] < mid):
            r += 1
        else:
            break
    
    if l == 0 and r == n * 2 - 1:
        return bool((n & 1) ^ (a[n - 1] < mid))
    
    if abs(n - 1 - l) < abs(n - 1 - r):
        return a[l] >= mid
    else:
        return a[r] >= mid

ok = 0
ng = n * 2

while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
A = np.array(readline().split(),np.int32)

def test(x):
    
    B = (A >= x)
    
    flag = np.zeros(N+N-1,np.bool)
    flag[:-1] = (B[:-1] == B[1:])
    
    """ version違いでボツ
    L = np.where(flag[:N])[0].max(initial=-1) + 1
    R = np.where(flag[N-1:-1])[0].min(initial=N-1) + N - 1
    """
    x = np.where(flag[:N])[0]
    L = x.max() + 1 if len(x) >= 1 else 0
    x = np.where(flag[N-1:-1])[0]
    R = x.min() + N - 1 if len(x) >= 1 else N+N-2
    if (N-1)-L > R-(N-1):
        return B[R]
    else:
        return B[L]

left = 0 
right = N+N+10 
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
l = 1
r = 2*n
while l < r-1:
    mid = (l+r)//2
    B = []
    C = []
    for i in range(0,2*n-1):
        B.append(A[i] >= mid)
        C.append(0)
    for i in range(1,2*n-1):
        if B[i-1] == B[i]:
            C[i] = 1
    for i in range(0,2*n-2):
        if B[i+1] == B[i]:
            C[i] = 1
    mi = 2*n
    ans = False
    for i in range(0,2*n-1):
        if C[i] == 1:
            if abs(i-n+1) < mi:
                mi = abs(i-n+1)
                ans = B[i]
    if mi == 2*n:   
        ans = ((n+1)%2)^B[n-1]
    if ans == True:
        l = mid
    else:
        r = mid
print(l)

Solution (Python):
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)

Solution (Python):
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    lo, hi = 1, 2 * n
    m = n - 1
    while lo + 1 < hi:
        mid = (lo + hi) / 2
        b = [x >= mid for x in a]
        t = b[0]
        for i in xrange(1, n):
            if b[m-i] == b[m-i+1]:
                t = b[m-i]
                break
            if b[m+i] == b[m+i-1]:
                t = b[m+i]
                break
        if t:
            lo = mid
        else:
            hi = mid
    print lo
main()

Solution (Python):



N = int(input())
a = [0] + list(map(int, input().split()))

def check(n):
	b = [False]*(len(a))
	for i in range(1, len(a)):
		if a[i] >= n:
			b[i] = True
		else:
			b[i] = False

	r = int(1e9)
	l = int(1e9)
	rb = b[N]
	lb = b[N]
	for i in range(1, N):
		if lb == b[N-i]:
			l = i
			break
		else:
			lb = b[N-i]
		
	for i in range(1, N):
		if rb == b[N+i]:
			r = i
			break
		else:
			rb = b[N+i]
	if r == int(1e9) and l == int(1e9):
		if N % 2 == 1:
			return b[N]
		else:
			return not b[N]
	else:
		if r < l:
			return rb
		else:
			return lb


def binarySearch(small, big):
	mid = (big + small) // 2
	if big - small <= 1:
		if check(small): return small
		else:            return big
	else:
		if not check(mid):
			return binarySearch(small, mid)
		else:
			return binarySearch(mid, big)

print(binarySearch(2, 2*N-2))