Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

k = int(input())

ans = 1
cnt = 0
while cnt < k:
    # print(ans, cnt)
    if ans <= 9:
        cnt+=1
        ans+=1
        continue
    li = list(map(int, list(str(ans))))
    flag=1
    for i in range(len(li)-1):
        if abs(li[i]-li[i+1]) > 1:
            ans+=1
            flag=0
            break
    if flag:
        cnt+=1
        ans+=1
print(ans-1)

### FIXED CODE ###

k = int(input())

ans = 1
cnt = 0
while cnt < k:
    # print(ans, cnt)
    if ans <= 9:
        cnt+=1
        ans+=1
        continue
    li = list(map(int, list(str(ans))))
    flag=1
    for i in range(len(li)-1):
        if abs(li[i]-li[i+1]) > 1:
            ans+=10**(len(li)-i-2)
            flag=0
            break
    if flag:
        cnt+=1
        ans+=1
print(ans-1)
### BUGGY CODE ###

import copy

N, M = map(int,input().split())

if M == 1:
    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]
    print(len(l))
else:
    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]
    l_tmp = copy.deepcopy(l)

    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]

    l_set = list(set(l) & set(l_tmp))
    l_tmp = copy.deepcopy(l)
    
    for i in range(M-2):
        L, R = map(int,input().split())
        l = [k+L for k in range(R-L+1)]

        l_set = list(set(l) & set(l_set))
        l_tmp = copy.deepcopy(l)
        
        if len(l_set) == 0:
            break

    print(len(l_set))

### FIXED CODE ###

N, M = map(int,input().split())

Ls, Rs = [0 for _ in range(M)],  [0 for _ in range(M)]

for i in range(M):
    L, R = map(int,input().split())
    Ls[i] = L
    Rs[i] = R
    
L_prime = max(Ls)
R_peime = min(Rs)

if L_prime > R_peime:
    print(0)
else:
    print(R_peime - L_prime + 1)
### BUGGY CODE ###

# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

N = int(input())
A = list(map(int, input().split()))
cnt1 = A.count(1)
cnt2 = A.count(2)
cnt3 = A.count(3)

dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0

# dp[c1][c2][c3]=
# 	1
# 	+dp[c1−1][c2][c3]∗(1個の皿が選ばれる確率)
# 	+dp[c1+1][c2−1][c3]∗(2個の皿が選ばれる確率)
# 	+dp[c1][c2+1][c3−1]∗(3個の皿が選ばれる確率)
# 	+dp[c1][c2][c3]∗(0個の皿が選ばれる確率)
# ↓式変形↓
# dp[c1][c2][c3]=
# 	1/(1−(0個の皿が選ばれる確率))
# 	+ dp[c1−1][c2][c3]*(1個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 	+ dp[c1+1][c2−1][c3]*(2個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 	+ dp[c1][c2+1][c3−1]*(3個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))


def func(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    #　1-(0個の皿が選ばれる確率), 繰り返し登場するので先に計算しておく
    prob = 1 - (N - c1 - c2 - c3) / N

    temp = 1 / prob
    if c1 > 0:
        temp += func(c1 - 1, c2, c3) * (c1 / N) / prob
    if c2 > 0:
        temp += func(c1 + 1, c2 - 1, c3) * (c2 / N) / prob
    if c3 > 0:
        temp += func(c1, c2 + 1, c3 - 1) * (c3 / N) / prob

    dp[c1][c2][c3] = temp
    return temp


print(func(cnt1, cnt2, cnt3))


### FIXED CODE ###

# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

N = int(input())
A = list(map(int, input().split()))
cnt1 = A.count(1)
cnt2 = A.count(2)
cnt3 = A.count(3)

dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0

# dp[c1][c2][c3]=1
# 	+dp[c1−1][c2][c3]∗(1個の皿が選ばれる確率)
# 	+dp[c1+1][c2−1][c3]∗(2個の皿が選ばれる確率)
# 	+dp[c1][c2+1][c3−1]∗(3個の皿が選ばれる確率)
# 	+dp[c1][c2][c3]∗(0個の皿が選ばれる確率)
# ↓式変形↓
# dp[c1][c2][c3]=1/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1−1][c2][c3]*(1個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1+1][c2−1][c3]*(2個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1][c2+1][c3−1]*(3個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))


def func(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    # 繰り返し登場するので先に計算しておく
    prob0 = (N - c1 - c2 - c3) / N

    temp = 1 / (1 - prob0)
    if c1 > 0:
        temp += func(c1 - 1, c2, c3) * (c1 / N) / (1 - prob0)
    if c2 > 0:
        temp += func(c1 + 1, c2 - 1, c3) * (c2 / N) / (1 - prob0)
    if c3 > 0:
        temp += func(c1, c2 + 1, c3 - 1) * (c3 / N) / (1 - prob0)

    dp[c1][c2][c3] = temp
    return temp


print(func(cnt1, cnt2, cnt3))
### BUGGY CODE ###

H,N = map(int,input().split())

A = []
B = []
for _ in range(N):
    i1,i2 = map(int,input().split())
    A.append(i1)
    B.append(i2)


# HPが0のとき
dp = {}
# 全てコスト無限大としておく
for hp in range(H+1):
    dp[hp] = float('inf')

dp[H] = 0
for hp in range(H,-1,-1):
    # 遷移 = 魔法を1つ使う
    for i in range(N):
        # 遷移先
        hp_next = hp - A[i]
        if hp_next < 0: hp_next = 0
        # 遷移先のコスト
        mp_next = dp[hp] + B[i]
        

        dp[hp_next] = min(dp[hp_next],mp_next)

print(dp[0])

### FIXED CODE ###

H,N = map(int,input().split())

A = []
B = []
for _ in range(N):
    i1,i2 = map(int,input().split())
    A.append(i1)
    B.append(i2)


# HPが0のとき
dp = {}
# 全てコスト無限大としておく
for hp in range(H+1):
    dp[hp] = float('inf')

dp[H] = 0
for hp in range(H,-1,-1):
    # 遷移 = 魔法を1つ使う
    for i in range(N):
        # 遷移先
        hp_next = hp - A[i]
        if hp_next < 0: hp_next = 0
        # 遷移先のコスト
        mp_next = dp[hp] + B[i]
        

        dp[hp_next] = min(dp[hp_next],mp_next)

print(dp[0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from numpy import array, int64
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

x = sum(H) // (A+B*(N-1))
H = array(sorted(H)).astype(int64)
 
while len(H):
    nH = H - B*x
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum(nH//D + (H%D>0)) <= x:
        print(x)
        break
    else:
        x += 1

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    su = p + px[v]
    sp[v] = su
    for di in d[v]:
        if not di == vp:
            f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

### FIXED CODE ###

from collections import deque
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = deque()
s.append(0)
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.popleft()
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])
### BUGGY CODE ###

N,M=map(int, input().split())

import networkx as nx

def connected_components(G):
    seen={}
    max_length = 0
    for v in G:
        if v not in seen:
            c = nx.algorithms.shortest_paths.single_source_shortest_path_length(G, v)
            #yield list(c)
            seen.update(c)
            length = len(c.values())
            if max_length<length:
                max_length=length
    return max_length

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    edges.append([i-1,j-1])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
#sg = nx.connected_components(G)
sg = connected_components(G)
print(sg)


### FIXED CODE ###

N,M=map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n # ノード数
        self.parents = [-1]*n # 各ノードごとのparent

    def find(self, x):
        # 自身が根であれば
        if self.parents[x]<0:
            return x
        # そうでなければ、再帰的に繰り返し、自身の根を探索
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # それぞれの根
        x = self.find(x)
        y = self.find(y)

        # 根が同一であれば
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x]+=self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    uf.union(i,j)

max_size = 0
for i in range(N):
    if uf.parents[i]<0:
        size = uf.size(i)
        if max_size<size:
            max_size = size
print(max_size)
### BUGGY CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

A = [int(input()) for _ in range(M)]

@lru_cache(100000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 1) + dfs(pos + 2)

print(dfs(0) % 1000000007)


### FIXED CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]

V = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    V[a].add(b)

C = [0] * N

for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    C[p] += x

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


dfs(0, 0)

print(" ".join([str(x) for x in ANS]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]
# V = [set() for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    # V[a].add(b)
    V[a].append(b)

C = [0] * N

for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    C[p] += x

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

numbers = input().split()
a = numbers[0]
b = numbers[1]
i = 1
while True:
    if a != i:
        i += 1
        continue
    else:
        if b < i:
            print(i - 1)
        else:
            print(i)
        
        break

### FIXED CODE ###

numbers = input().split()
a = int(numbers[0])
b = int(numbers[1])
i = 1
while True:
    if a != i:
        i += 1
        continue
    else:
        if b < i:
            print(i - 1)
            break
        else:
            print(i)
            break
### BUGGY CODE ###

import math
from collections import Counter
import itertools

def prime_factors(n):
  i = 2
  factors = []
  while i * i <= n:
    if n % i==0:
      n //= i
      factors.append(i)
    else:
      i += 1
  if n > 1:
    factors.append(n)
  return factors

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return sorted(divisors)

n=int(input())
num=math.factorial(n)
yakusu=make_divisors(num)

cnt=0
for i in yakusu:
  factors=list(map(lambda x:x+1,Counter(prime_factors(i)).values()))
  tmp=1
  for j in factors:
    tmp*=j
  if tmp==75:
    cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
e=[0]*(n+1)

#素因数分解をしている
for i in range(2,n+1):
  cur=i
  for j in range(2,i+1):
    while cur % j == 0:
      e[j] += 1
      cur //=j

def num(m):
  return len(list(filter(lambda x: x>=m-1,e)))

print(num(75)+ num(25)*(num(3)-1)+ num(15)*(num(5)-1)+ num(5)*(num(5)-1)*(num(3)-2)//2)
### BUGGY CODE ###

import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    visited = deque()
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            visited.append((x,y))
            if S[y-1][x] != '#' and (x, y-1) not in visited:
                un.append((x, y-1))

            if S[y+1][x] != '#' and (x, y+1) not in visited:
                if y+1 == H and x == W:
                    return dist
                un.append((x, y+1))

            if S[y][x-1] != '#' and (x-1, y) not in visited:
                un.append((x-1, y))

            if S[y][x+1] != '#' and (x+1, y) not in visited:
                if y == H and x+1 == W:
                    return dist
                un.append((x+1, y))
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = [list('#'+input()+'#') for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '#' and not visited[dy][dx]:
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    N, M = list(map(int, input().split()))

    L, R = [], []
    for i in range(M):
        l, r = list(map(int, input().split()))
        L.append(l)
        R.append(r)

    key_set = {i for i in range(L[0], R[0]+1)}
    for i in range(1, M):
        key_set = key_set & {i for i in range(L[i], R[i]+1)}

    print(len(key_set))


if __name__ == '__main__':
    main()

### FIXED CODE ###

N, M = list(map(int, input().split()))

L, R = [], []
for i in range(M):
    l, r = list(map(int, input().split()))
    L.append(l)
    R.append(r)

ans = min(R) - max(L) + 1
if ans >= 0:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

from collections import deque
def bfs(start, goal, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            for next2_node in g[next1_node]:
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1)]

    for _ in range(m):
        u, v = map(int, input().split())
        g[u].append(v)

    s,t = map(int, input().split())
    

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, visited)
    print(visited[t])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def bfs(start, goal, g, n, visited):
    visited1 = [False]*(n+1)
    visited2 = [False]*(n+1)
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            if visited1[next1_node]: continue
            visited1[next1_node] = True
            for next2_node in g[next1_node]:
                if visited2[next2_node]: continue
                visited2[next2_node] = True
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1)]

    for _ in range(m):
        u, v = map(int, input().split())
        g[u].append(v)

    s,t = map(int, input().split())
    

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, n, visited)
    print(visited[t])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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


final_ans = 0
num = 1000000007
a.sort()

for i in range(n-1):
    if i != 0:
        if a[i] == a[i-1]:
            final_ans += ans
            final_ans %= num
            continue
        else:
            ans = 0
            for j in range(i+1, n):
                ans += (a[i] ^ a[j])
                ans %= num
            final_ans += ans
            final_ans %= num
    else:
        ans = 0
        for j in range(i+1, n):
            ans += (a[i] ^ a[j])
            ans %= num
        final_ans += ans
        final_ans %= num

print(final_ans)

### FIXED CODE ###

import numpy as np

MOD = 10**9 + 7
n = int(input())
a = np.array(input().split(), np.int64)
max_num = np.max(a)
digit_num = len(format(max_num, 'b'))
ans = 0
for digit in range(digit_num):
    b = (a >> digit) & 1
    one = np.count_nonzero(b)
    zero = n - one
    ans += 2 ** digit * (one * zero)
    ans %= MOD

print(ans)
### BUGGY CODE ###

class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        self.__size = size
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(a)
        bit.add(a, 1)

    return s


def check2(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list) -> int:
    def check(x: int)->int:
        S = [0] * (N + 1)
        for i in range(N):
            if x <= A[i]:
                S[i + 1] = S[i] + 1
            else:
                S[i + 1] = S[i] - 1

        # m = min(S)
        # for i in range(N + 1):
        #     S[i] -= m - 1

        # bit = BIT(max(S))
        bit = BIT(2 * N + 1)
        s = 0
        for a in S:
            s += bit.sum(a + N)
            bit.add(a + N, 1)

        return s

    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(alpha[m]) >= (N * (N + 1)) // 2:
            l = m
            if m == N - 1:
                break
            if 2 * check(alpha[m + 1]) < (N * (N + 1)) // 2:
                break
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())

maze = [input() for _ in range(H)]

light_max = 0

def light(xx, yy):
    drc = [(-1, 0), (1, 0), (0, 1), (0, -1)] 
    ans = 1
    for dx, dy in drc:
        xx0 = xx + dx
        yy0 = yy + dy
        while 0 <= xx0 <= W-1 and 0 <= yy0 <= H-1:
            if maze[yy0][xx0] == '#':break
            ans += 1
            xx0 += dx
            yy0 += dy
    return ans

for hh in range(H):
    for ww in range(W):
        if maze[hh][ww] == '#':continue
        area = light(ww, hh)
        light_max = max(light_max, area)

print(light_max)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))