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

from collections import deque

dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, 0, 1))
    sp = -1
    while len(q):
        i, j, path = q.popleft()
        if i == H-1 and j == W-1:
            sp = path
            break
        if S[i][j] != '.' and S[i][j] < path:
            continue
        S[i][j] = path
        for d in dirs:
            ni, nj = i+d[0], j+d[1]
            if ni >= 0 and nj >= 0 and ni < H and nj < W and S[ni][nj] != '#':
                q.append((ni, nj, path+1))
    if sp == -1:
        print(sp)
    else:
        ans = 0
        for i in range(H):
            for j in range(W):
                if S[i][j] != '#':
                    ans += 1
        print(ans - sp)


if __name__ == "__main__":
    main()


### FIXED CODE ###

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("#", "")) for row in s])
    scan = [(0, 0, 1)]  # i, j, cost
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    if path[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(white - path[H-1][W-1])


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

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

ret_rev = []

i, j = len(s) - 1, len(t) - 1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ret_rev.append(s[i])
        i, j = i - 1, j - 1
    elif dp[i + 1][j + 1] == dp[i + 1][j]:
        i, j = i, j - 1
    else: # i.e. dp[i + 1][j + 1] == dp[i][j + 1]
        i, j = i - 1, j

ret = "".join(ret_rev[::-1])

print(ret)


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

ret_rev = ""

i, j = len(s) - 1, len(t) - 1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ret_rev += s[i]
        i, j = i - 1, j - 1
    elif dp[i + 1][j] == dp[i][j]:
        i, j = i - 1, j
    else: # i.e. dp[i][j + 1] == dp[i][j]
        i, j = i, j - 1

ret = ret_rev[::-1]

print(ret)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    total = [0] * len(new_s) # ブロックごとに、切った後~進んだ分の増えたホワイトチョコの個数を管理
    for k in range(w):
        tmp_list = [0]*len(new_s) # ブロックごとに、1つ進めて増えるホワイトチョコを管理
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total: # 1つでもKを越えていたら直前で切る
            if m > K:
                cnt += 1
                total = tmp_list
                break
    if not flag:
        ans = min(ans, cnt)
print(ans)






### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(w):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total:
            flag_2 = 1
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
        # if flag_2:
        #     for m in total:
        #         if m == K and k != w - 1:
        #             cnt += 1
        #             total = [0]*len(new_s)
        #             break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

N, K, L = [int(_) for _ in input().split()]


class UFT():
    def __init__(self):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    memo[Road.find(i)][Railway.find(i)] += 1
print(' '.join(str(memo[Road.find(i)][Railway.find(i)])
               for i in range(1, N + 1)))


### FIXED CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))
### BUGGY CODE ###

import sys
import heapq


def dfs(u,s,target, route=None):
    if(route == None):
        route=[]
    route.append(u)
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if e_2[j] not in route:
                count = s + e_w[j]
                dfs(e_2[j],count,target,route[0:])


v,e,r=map(int, input().split());

vs=[0]*v;

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(v):
    vs[i] = 0;
for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

for i in range(v):
    h = []
    dfs(r,0,i)
    if(len(h) != 0):
        print(heapq.heappop(h))
    else:
        print("INF")



### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

from numba import njit
import numpy as np
@njit
def dfs(v,c,h,stay):
    # hを更新
    todo=[[v,c]]
    while todo:
        vv,cc=todo.pop()
        x,y=divmod(vv,n)
        for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
            nx,ny=x+dx,y+dy
            if 0<=nx<n and 0<=ny<n:
                nv=nx*n+ny
                if h[nv]>cc:
                    h[nv]=cc
                    todo.append([nv,cc+stay[nv]])
                    #dfs(nv,c+stay[nv],h,stay)

@njit
def main(n,p):
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0

    for v in p:
        c=h[v]
        ans+=c
        stay[v]=0
        dfs(v,c,h,stay)
    print(ans)

    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    n=int(input())
    p=np.array(list(map(int,input().split())),np.int32)
    p-=1
    main(n,p)

### FIXED CODE ###

from numba import njit
import numpy as np
@njit
def dfs(v,c,h,stay):
    # hを更新
    x,y=divmod(v,n)
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx,ny=x+dx,y+dy
        if 0<=nx<n and 0<=ny<n:
            nv=nx*n+ny
            if h[nv]>c:
                h[nv]=c
                dfs(nv,c+stay[nv],h,stay)

@njit
def main(n,p):
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0

    for v in p:
        c=h[v]
        ans+=c
        stay[v]=0
        dfs(v,c,h,stay)
    print(ans)

    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    n=int(input())
    p=np.array(list(map(int,input().split())),np.int32)
    p-=1
    main(n,p)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

limit = pow(10, 18)

ans = 0
unfair = False
for v in range(k):
    if a == b and b == c:
        break
    na = b + c
    nb = a + c
    nc = a + b
    a = na
    b = nb
    c = nc
ans = a - b
if abs(ans) > limit:
    print("Unfair")
else:
    print(ans)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

if k % 2 == 0:
    print(a - b)
else:
    print(b - a)
### BUGGY CODE ###

M = 15140366
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')



### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
import numpy as np
INF = int(1e9)
dist = np.full((h+2, w+2), INF)

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i, 0] = 0
    dist[i, -1] = 0
for j in range(w+2):
    dist[0, j] = 0
    dist[-1, j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


n, m, k = map(int, input().split())


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(chain[i] - friends[i] - 1)

print(*ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)

    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True

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

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


n, m, k = map(int, input().split())


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c, d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(uf.size(i) - friends[i] - 1)

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

H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
s=[[] for _ in range(H)]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  s[h-1].append(w-1)
 
qh=[]
qw=[]
maxh=max(sumh)
maxw=max(sumw)
for i in range(H):
  if maxh==sumh[i]:
    qh.append(i)
for i in range(W):
  if maxw==sumw[i]:
    qw.append(i)
 
#print(s,H,W,sumh,sumw,qh,qw)
for i in qh:
  for j in qw:
    if j not in s[i]:
      print(maxh+maxw)
      exit()
 
print(maxh+maxw-1)

### FIXED CODE ###

H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
bomb=[]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  bomb.append((h,w))

maxh=max(sumh)
maxw=max(sumw)
ch=sumh.count(maxh)
cw=sumw.count(maxw)

cnt=0
for h,w in bomb:
  if sumh[h-1]==maxh and sumw[w-1]==maxw:
    cnt+=1

if cnt==ch*cw:
  print(maxh+maxw-1)
else:
  print(maxh+maxw)
### BUGGY CODE ###

n,m = map(int,input().split())
x = []
y = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
ans = 0

while(1):
    if m == 0:
        break
    if y[x.index(min(x))] <= m:
        tmp = x.index(min(x))
        ans += min(x)*y[x.index(min(x))]
        m -= y[x.index(min(x))]
        x.pop(tmp)
        y.pop(tmp)
    else:
        ans += min(x)*m
        m = 0
print(ans)

### FIXED CODE ###

from operator import itemgetter

n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = 0
a.sort(key=itemgetter(0))
i = 0
while(1):
    if m == 0:
        break
    if a[i][1] <= m:
        ans += a[i][0]*a[i][1]
        m -= a[i][1]
        i += 1
    else:
        ans += a[i][0]*m
        m = 0
print(ans)
### BUGGY CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

ar_bool = [(min(P[:i+1]) == P[i]) for i in range(N)]
print(sum(ar_bool))

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

#ABC132_C
N=int(input())
d=list(map(int,input().split()))

L=2
R=2*10**5


while 1:
    #print('Lis',L)
    #print('Ris',R)
    k=int((L+R)/2)
    #print('kis',k)
    ABC_num=0
    for i in range(len(d)):
        if d[i]<k:
            ABC_num+=1
    #print('ABC_num_is',ABC_num)
    if ABC_num==N/2:
        k_start=k
        break
    elif (L+1)==R:
        k_start=0
        break
    elif ABC_num<N/2:
        L=k
    else:
        R=k       
if k_start!=0:
    k=k_start+1
    while 1:
        ABC_num=0
        for i in range(len(d)):
            if d[i]<k:
                ABC_num+=1
        if ABC_num==N/2:
            k+=1
        else:
            k_r=k-1
            break
    k=k_start-1
    while 1:
        ABC_num=0
        for i in range(len(d)):
            if d[i]<k:
                ABC_num+=1
        if ABC_num==N/2:
            k-=1
        else:
            k_l=k+1
            break
    #print('k_ris',k_r)
    #print('k_lis',k_l)
    print(k_r-k_l+1)
else:
    print(0)

### FIXED CODE ###

#ABC132_C
N=int(input())
d=list(map(int,input().split()))

d.sort()

ans=d[int(N/2)]-d[int(N/2-1)]
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
t=int(s)
dict={}
sum=0
for i in range(n):
    for j in range(i+1,n):
        """string=str(i)+"_"+str(j)
        if string not in dict.keys():
            dict[string]=0"""
        num=s[i:j+1]
        num=int(num)
        if num%2019==0:
            sum+=1
        
print(sum)

### FIXED CODE ###

import sys
import collections as coun
sys.setrecursionlimit(10000000)
s=input()
n=len(s)
def mod10(x):
    return (10**(x%224))%2019
dp=[-1]*n
tmp=0
for i in reversed(range(n)):
    if i==n-1:
        dp[i]=int(s[i])
    else:
        dp[i]=(dp[i+1]+int(s[i])*pow(10,n-1-i,2019))%2019

#print(dp)
p=-1
for i in range(len(dp)-1):
    if dp[i]==dp[i+1]:
        dp[i]=p
        p=p-1

#print(dp)

c=coun.Counter(dp)
sum=0
for v in c.values():
    sum+=v*(v-1)//2
#print(sum)
for i in dp:
    if i==0:
        sum+=1
#print(sum)
if dp[-1]==0:
    sum=sum-1
print(sum)
### BUGGY CODE ###

N,M = map(int,input().split())
li = []
numb = []
ans = ''
for i in range(M):
  a,b = map(int,input().split())
  if a == 1:
    li.append(b)
  elif b == N:
    numb.append(a)
for i in range(len(li)):
  if li[i] in numb:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
li = []
numb = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        li.append(b)
    elif b == N:
        numb.append(a)
ans = set(li) & set(numb)
if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
nums = [int(input()) for _ in range(N)]

for i in range(len(nums)):
  pop = nums.pop(i)
  print(max(nums))
  nums.insert(i,pop)

### FIXED CODE ###

import numpy as np
N = int(input())
nums = [int(input()) for _ in range(N)]
nums = np.array(nums)
max_num = max(nums)
max_index = np.where(nums == nums.max())[0]

if len(max_index) == 1:
  for i in range(len(nums)):
    if i == max_index[0]:
      print(sorted(nums)[-2])
    else:
      print(max_num)
else:
  for i in range(len(nums)):
    print(max_num)