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



Sample input:
4
1 6 3 7 4 5 2


Sample output:
4

Submission status: Wrong Answer

Solution code:
#editorial
#ある数以下、以上が連続していればそれが保持
n = int(input())
*a,=map(int, input().split())

mx=2*n+1
mn=0

while mx-mn>1:
    mid=(mx+mn)//2
    for i in range(n-1):
        if (a[n+i-1]>=mid & a[n+i]>=mid) |( a[n-i-1]>=mid & a[n-2-i]>=mid):
            mn=mid
            break
        if (a[n+i-1]<mid & a[n+i]<mid) |( a[n-i-1]<mid & a[n-2-i]<mid):
            mx=mid
            break
    mx=mid
print(mn)

Submission status: Wrong Answer

Solution code:
N=int(input())
print(N)

Submission status: Wrong Answer

Solution code:
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
    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)

Submission status: Wrong Answer

Solution code:
N = int(input())
print(N)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))

print(N)

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    S = SI(); T = SI()
    ans = 2*N
    for l in range(N-1,-1,-1):
        flag = True
        for i in range(l+1):
            if S[N-1-i] != T[l-i]:
                flag = False
                break
        if flag:
            ans -=(l+1)
            break
    print(ans)
    return

def examB():
    N, x = LI()
    d = defaultdict(bool)
    if x==1 or x==2*N-1:
        print("No")
        return
    print("Yes")
    ans = [0]*(2*N-1)
    ans[N-1] = x
    d[x] = True

    ans[N] = x+1
    ans[N-2] = x-1
    d[x+1] = True
    d[x-1] = True
#    print(d); print(ans)
    cur = 1
    for j in range(N-2):
        while(d[cur]):
            cur +=1
        ans[j] = cur
        cur +=1
    for j in range(N+1,2*N-1):
        while(d[cur]):
            cur +=1
        ans[j] = cur
        cur +=1
    for v in ans:
        print(v)
    return

def examD():
    N = I()
    A = LI()
    next = [0]*(2*N-3)
    for i in range(1,2*N-2):
        cur = [A[i-1],A[i],A[i+1]]
        cur.sort()
        next[i-1] = cur[1]
    ans = next[2*N-4]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
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):
    # 答は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 # 答はleft以上
right = N+10 # 答はright未満
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

Submission status: Wrong Answer

Solution code:
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):
    # 答は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-2) + N
    """
    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 if len(x) >= 1 else N+N-2
    if (N-1)-L > R-(N-1):
        return B[R]
    else:
        return B[L]

left = 0 # 答はleft以上
right = N+10 # 答はright未満
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

test(2)

Submission status: Wrong Answer

Solution code:
n = int(input())
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
z = (2*N-1) // 2 - 1

left = sorted(A[:-2])[z]
center = sorted(A[1:-1])[z]
right = sorted(A[2:])[z]

ans = sorted([left, center, right])[1]
print(ans)

Submission status: Wrong Answer

Solution code:
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 ans == True:
        l = mid
    else:
        r = mid
print(l)

Submission status: Wrong Answer

Solution code:
a=int(input())
b=input()
print(sorted(list(map(int,b.split())))[a-1])

Submission status: Wrong Answer

Solution code:
a=int(input())
b=input()
print(sorted(list(map(int,b.split())))[a])

Submission status: Wrong Answer

Solution code:

def calc(a):
    if len(a) == 1:
        return a[0]
    else:
        b = []
        for i in range(len(a) - 2):
            b.append(sorted(a[i:i+2])[1])
        return calc(b)

n = input()
a = list(map(int, input().split()))
print(calc(a))

Submission status: Wrong Answer

Solution code:

def calc(a):
    if len(a) == 1:
        return a[0]
    else:
        b = []
        for i in range(len(a) - 2):
            b.append(sorted(a[i:i+2])[1])
        return calc(b)
 
n = input()
a = list(map(int, input().split()))
print(calc(a))

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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

def takeMid(x, y, z):
	tmp = [x, y, z]
	tmp.sort()
	return tmp[1]

if N == 2:
	print(2)
else:
	one = takeMid(a[N-2], a[N-1], a[N])
	two = takeMid(a[N-1], a[N], a[N+1])
	three = takeMid(a[N], a[N+1], a[N+2])

	if one == two:
		print(one)
	elif two == three:
		print(two)
	elif three == one:
		print(one)
	else:
		print(N)

Submission status: Wrong Answer

Solution code:
N = input()
M = N*2-1
L = map(int, raw_input().split())
L2 = [0 for i in xrange(M-2)]

for i in xrange(M-2):
    L2[i] = sorted([L[i], L[i+1], L[i+2]])[1]

if len(L2) == len(set(L2)):
    print N
    exit()

#c = (N*2-7)/2
#print sorted(L2[c+1:c+4])[1]
c = (N*2-7)/2
x1 = sorted(L2[c:c+3])[1], sorted(L2[c+1:c+4])[1]
c = (N*2-7)/2+1
x2 = sorted(L2[c:c+3])[1], sorted(L2[c+1:c+4])[1]
x = (x1[0], x1[1], x2[1])
if x[0] == x[1] or x[1] == x[2]:
    print x[1]
else:
    print N

Submission status: Wrong Answer

Solution code:
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>=1 and now[l/2]+1<=l:
        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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

from statistics import median

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())
nums = get_nums_l()

while len(nums) > 1:
    new_nums = []

    for i in range(1, len(nums)-1):
        new_nums.append(median(nums[i-1:i+2]))

    nums = new_nums

print(nums[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import *
from itertools import *
import random

def bf(n):
    variations = defaultdict(list)
    for comb in permutations(list(range(1,n+1))):
        top = sim(comb)
        variations[top].append(comb)
#        if top not in variations:
            # print(top, comb)
            # variations[top].append(comb)
        # if top != comb[ len(comb) // 2 ]:
        #     print("exception!")
        #     print("comb, result = ", comb, top)
    for key in variations:
        print(key, ":")
        for v in variations[key]:
            print(" ", v)
    # print(variations)
    
def sim(comb, print_flag = False):
    comb = list(comb)
    if print_flag:
        print("-------")
        print(comb)
    cnt = 1
    while len(comb) != 1:
        n_comb = []
        for i in range(len(comb)-2):
            arr = comb[i:i+3]
            arr.sort()
            n_comb.append(arr[1])
        comb = n_comb
        if print_flag:
            print("   " * cnt + str(comb))
        cnt += 1
    return comb[0]

def sim2(comb, print_flag = False):
    comb = list(comb)
    if print_flag:
        print("-------")
        print(comb)
    cnt = 1
    while len(comb) != 1:
        mid = len(comb) // 2
        if comb[mid] == comb[mid + 1] or comb[mid] == comb[mid - 1]:
            return comb[mid]
        if comb[mid-1] <= comb[mid] <= comb[mid+1] or \
           comb[mid-1] >= comb[mid] >= comb[mid+1]:
            return comb[mid]

        n_comb = []
        for i in range(len(comb)-2):
            arr = comb[i:i+3]
            arr.sort()
            n_comb.append(arr[1])
        comb = n_comb
        if print_flag:
            print("   " * cnt + str(comb))
        cnt += 1

    return comb[0]

def rand(n):
    while True:
        arr = list(range(1,n+1))
        random.shuffle(arr)
        if sim(arr) != sim2(arr):
            print("error!")
            sim(arr, True)
            sim2(arr, True)
            
            

# bf(3)
# bf(5)
# bf(7)
# bf(9)
# bf(11)
#rand(17)
#rand(33)

def main():
    N = int(input())
    arr = list(map(int,input().split()))
    print(sim2(arr))

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import *
from itertools import *
import random

def bf(n):
    variations = defaultdict(list)
    for comb in permutations(list(range(1,n+1))):
        top = sim(comb)
        variations[top].append(comb)
#        if top not in variations:
            # print(top, comb)
            # variations[top].append(comb)
        # if top != comb[ len(comb) // 2 ]:
        #     print("exception!")
        #     print("comb, result = ", comb, top)
    for key in variations:
        print(key, ":")
        for v in variations[key]:
            print(" ", v)
    # print(variations)
    
def sim(comb, print_flag = True):
    comb = list(comb)
    if print_flag:
        print("-------")
        print(comb)
    cnt = 1
    while len(comb) != 1:
        n_comb = []
        for i in range(len(comb)-2):
            arr = comb[i:i+3]
            arr.sort()
            n_comb.append(arr[1])
        comb = n_comb
        if print_flag:
            print("   " * cnt + str(comb))
        cnt += 1
    return comb[0]

def sim2(comb, print_flag = True):
    comb = list(comb)
    while len(comb) != 1:
        mid = len(comb) // 2
        if comb[mid] == comb[mid + 1] or comb[mid] == comb[mid - 1]:
            return comb[mid]

        n_comb = []
        for i in range(len(comb)-2):
            arr = comb[i:i+3]
            arr.sort()
            n_comb.append(arr[1])
        comb = n_comb

    return comb[0]

def rand(n):
    while True:
        arr = list(range(1,n+1))
        random.shuffle(arr)
        sim(arr)

# bf(3)
# bf(5)
# bf(7)
# bf(9)
# bf(11)
# rand(11)

def main():
    N = int(input())
    arr = list(map(int,input().split()))
    print(sim2(arr))

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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

Submission status: Time Limit Exceeded

Solution code:

def find_medium(first, second, third):
    return sorted([first,second,third])[1]

if __name__ == '__main__':
    n = int(input())
    a = [int(x) for x in input().split()]
    n -= 1
    row_count = (2 * n) - 1
    curr_row = a
    while(n > 0):
        new_row = []
        for i in range(row_count):
            new_row.append(find_medium(curr_row[i], curr_row[i+1], curr_row[i+2]))
        curr_row = new_row
        n -= 1
        row_count = (2 * n) - 1
    print(curr_row[0])

Submission status: Time Limit Exceeded

Solution code:
def median(x):
    return sorted(list(x))[1]

def top(l):
    while len(l) > 1:
        l = [median(x) for x in list(zip(l, l[1:], l[2:]))]
    return l[0]

input()
print(top([int(x) for x in input().split()]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
    # 答は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 # 答はleft以上
right = N+N+10 # 答はright未満
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

Submission status: Accepted

Solution code:
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:   #specialfall
        ans = ((n+1)%2)^B[n-1]
    if ans == True:
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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))

Submission status: Runtime Error

Solution code:

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

from statistics import median

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())
nums = get_nums_l()

while len(nums) > 1:
    print(nums)
    new_nums = []

    for i in range(1, len(nums)-1):
        new_nums.append(median(nums[i-1:i+2]))

    nums = new_nums

print(nums[0])

Submission status: Runtime Error

Solution code:
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):
    # 答はx以上
    B = (A >= x)
    # 連番の左側にフラグを立てる
    flag = np.zeros(N+N-1,np.bool)
    flag[:-1] = (B[:-1] == B[1:])
    # 最寄りの連番を探す
    L = np.where(flag[:N])[0].max(initial=-1) + 1
    R = np.where(flag[N-1:-1])[0].min(initial=N-2) + N
    if (N-1)-L > R-(N-1):
        return B[R]
    else:
        return B[L]

left = 0 # 答はleft以上
right = N+10 # 答はright未満
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define N 200005
using namespace std;

inline void rd(int &x){
	x=0;char ch=0;int w=0;
	while(!isdigit(ch)) ch=getchar(),w|=ch=='-';
	while( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=w?-x:x;
}

int l,r;
int n,m;
int a[N],b[N];

bool ok(int x){
	for(int i=1;i<=m;i++)
		b[i]=(a[i]>=x);
	for(int i=0;i<n;i++){
		if((b[n-i] and b[n-i-1]) or (b[n+i] and b[n+i+1])) return 1;
		if((!b[n-i] and !b[n-i-1]) or (!b[n+i] and !b[n+i+1])) return 0;
	}
	return b[1];
}
signed main(){
	rd(n);m=n*2-1;l=1;r=m+1;
	for(int i=1;i<=m;i++) rd(a[i]);
	while(l<r){
		int mid=(l+r)>>1;
		ok(mid) ? l=mid+1 : r=mid;
	}
	cout<<l-1;
}

Submission status: Runtime Error

Solution code:
#coding:utf8
import numpy as np

def mid(a, b, c):
	li = [a,b,c]
	li.sort()
	return li[1]

N = int(input())
an = list(map(int,input().split()))
np.set_printoptions(precision=0)

# N = 4
# an = [1,6,3,7,4,5,2]
a = np.empty((N,2*N-1))
for i in range(2*N-1):
	a[N-1,i] = an[i]
# print(a)

# print(a[1,1])

# print(mid(a[0,0],a[0,1],a[0,2]))

for i in range(N-2, 0-1, -1):
	for j in range(0, 2*(i+1)-2+1):
		# print(i)
		# print(j)
		a[i,j] = mid(a[i+1,j],a[i+1,j+1],a[i+1,j+2])
# print(a)
print(int(a[0,0]))