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

def main():
    import sys

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

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

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

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

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

    dp = tuple(
        tuple(
            [-1.0] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    dp[0][0][0] = 0.0
    # dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, c3))


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントの仕方を簡素にした


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

import itertools
H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

for i in range(M):
  h, w = map(int, input().split())
  h-=1
  w-=1
  row[h]+=1
  col[w]+=1
  mat[h][w]+=1

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

x=min([min([mat[i][j] for j in cc]) for i in rr])

if x==0:
  print(r+c)
else:
  print(r+c-1)

### FIXED CODE ###

H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[]

for i in range(M):
  h, w = map(int, input().split())
  row[h-1]+=1
  col[w-1]+=1
  mat.append((h-1,w-1))
  
r=max(row)
c=max(col)

rr=[1 if row[i]==r else 0 for i in range(H)]
cc=[1 if col[i]==c else 0 for i in range(W)]

x=0
for k in mat:
  if rr[k[0]]==1 and cc[k[1]]==1:
    x+=1

if sum(rr)*sum(cc)==x:
  print(r+c-1)
else:
  print(r+c)
### BUGGY CODE ###

N, Q = input().split(' ')
N = int(N)
Q = int(Q)

S = input()
AC ='AC'

for i in range(Q):
    l_i, r_i = input().split(' ')
    l_i = int(l_i)
    r_i = int(r_i)
    print(S[l_i-1:r_i].count(AC))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l_i, r_i = map(int, input().split())
    print(t[r_i-1] - t[l_i-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[a].add(b)
  E[b].add(a)

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)
#print(DU)
#print(DV)
mx = 0
for du,dv in zip(DU,DV):
  if du < dv:
    mx = max(dv,mx)
print(mx-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[a].add(b)
  E[b].add(a)

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)
#print(DU)
#print(DV)
mx = 0
for du,dv in zip(DU,DV):
  if du < dv:
    mx = max(dv,mx)
print(mx-1)
### BUGGY CODE ###

N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))
    if t[i] >= tmax:
        tmax = t[i]


c_timeline = [[0 for _ in range(C)] for _ in range(2*tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i]-1
    for j in range(2*S-1, 2*T+1):
        c_timeline[j][channel] = 1

rokuga = []
for timeline in c_timeline:
    rokuga.append(sum(timeline))

print(max(rokuga))



### FIXED CODE ###

N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

rokuga = 0
for timeline in c_timeline:
    time = sum(timeline)
    if rokuga < time:
        rokuga = time

print(rokuga)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n,x,y = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]

for i in range(n-1):
    graph[i][i+1] = 1
    graph[i+1][i] = 1
    
graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

ans = floyd_warshall(graph )

for i in range(1,n):
    print(int(np.count_nonzero(ans == i)/2))

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(abs(i-j) , abs(i-x)+1+abs(j-y), abs(i-y)+1+abs(j-x)) ]+=1
        
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

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

for i in range(q):
    a.sort()
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
        elif a[j] > b:
            break
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [0]*100010
ans = sum(a)

for i in a:
    l[i] += 1

for i in range(q):
    b, c = map(int, input().split())
    ans += (c - b)*l[b]
    l[c] += l[b]
    l[b] = 0
    print(ans)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	ans = 0
	for x in a:
		ans += lcm // x
		ans %= MOD
	print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= MOD
	ans = 0
	for x in a:
		ans += lcm * pow(x, MOD-2, MOD)
		ans %= MOD
	print(ans)
### BUGGY CODE ###

N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    tmp=min(ans)
    a_list.append(tmp)
    graph[i].remove(tmp)
    graph[j].remove(tmp)
print(max(a_list))
for i in a_list:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N - 1)


def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1


dfs()
for i in ans:
    print(i)
### BUGGY CODE ###

from itertools import accumulate
n, K = map(int,input().split())
A = list(map(int,input().split()))
b = [0 for _ in range(n+1)]

for _ in range(min(50, K)):
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    ac = list(accumulate(b))
    A = ac
    b = [0 for _ in range(n+1)]
    
print(*ac[:-1])

### FIXED CODE ###

n, K = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(K):
    b = [0 for _ in range(n+1)]
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]

    A = b[:-1]
    if all(a == n for a in A):
        break
print(*A)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for j in range(Q):
    rep = [i for i in A if i != B[j]]
    for _ in range(len(A) - len(rep)):
        rep.append(C[j])
    A = rep[::]

    print(sum(A))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())

B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

d = [0] * (10**5 + 7)
for a in A:
    d[a] += 1
sum_a = sum(A)
for j in range(Q):
    before = d[C[j]]
    d[C[j]] += d[B[j]]
    sum_a -= d[B[j]] * B[j]

    sum_a += (d[C[j]] - before) * C[j]
    d[B[j]] = 0
    print(sum_a)
### BUGGY CODE ###

# 000~999で決め打ちして数える
n = int(input())
s = input()
ans = 0

for i in range(0, 1000):
    t = format(i, "0>3")
    idx = 0
    for c in s:
        if c == t[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

# 000~999で決め打ちして数える
# TLEになるんだけどこれそんなに重いか？？？？？

n = int(input())
s = input()
ans = 0

for i in range(0, 1000):
    t = format(i, "0>3")
    idx = 0
    for c in s:
        if c == t[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

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

import sys
sys.setrecursionlimit(10 ** 7)


def dfs(tree, count, p):
    # print(p, tree[p])
    for i in tree[p]:
        count[i] += count[p]
        dfs(tree, count, i)


def solve(tree, count):
    from collections import deque
    stk = deque([1])

    while stk:
        p = stk.pop()
        for i in tree[p]:
            count[i] += count[p]
            stk.append(i)


def remove_parents(tree, p):
    for i in tree[p]:
        tree[i].remove(p)
        remove_parents(tree, i)


def main():
    N, Q = map(int, input().split())
    tree = {i+1: set() for i in range(N)}
    count = {i+1: 0 for i in range(N)}

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

    for _ in range(Q):
        p, x = map(int, input().split())
        count[p] += x

    # print(count)

    # visited = {k+1: False for k in range(N)}
    # visited[1] = True

    remove_parents(tree, 1)
    # print(tree)
    # dfs(tree, count, 1)
    solve(tree, count)

    ans = [str(count[k]) for k in sorted(count.keys())]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict, deque


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

    tree = defaultdict(list)
    counter = defaultdict(int)
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p, x = map(int, input().split())
        counter[p] += x

    # bfs
    q = deque([1])
    visited = {1}

    while q:
        i = q.popleft()

        for j in tree[i]:
            if j not in visited:
                q.append(j)
                counter[j] += counter[i]
                visited.add(j)

    counts = [counter[i] for i in range(1, N+1)]
    ans = " ".join(map(str, counts))
    print(ans)



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

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  for i in range(k-sa):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if ans==1:
        bk3=max(mansbk,pansbk)
      elif bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=1 if (k-sa-i)%2==1 else bk1
        break
    else:
      ans=0 if (k-sa-i)%2==0 else d
      break
    if ans==mbk:
      ans=mbk if (k-sa-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=mbk if (k-i)%2==0 else bk1
        break
      else:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
tmp = M // N
ansMax = 0
for i in range(1, tmp + 1):
    ansTmp = M - ((N - 1) * i)
    if ansTmp % i == 0:
        ansMax = i

print(ansMax)

### FIXED CODE ###

N, M = map(int, input().split())
tmp = M // N
ansMax = 0
y = []
for i in range(1, (int(M ** (0.5)) + 1)):
    if M % i == 0:
        y.append(i)
        if i != M // i:
            y.append(M // i)
y.sort()

for i in y:
    if i <= tmp:
        ansMax = i
    else:
        break
print(ansMax)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    print(0)
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    print(N-1)
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        print(mid)
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left+1, m-1
    else:
        left, right = m+1, right-1


### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

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

A = list(map(lambda x: x%(1*10**9 + 7), A))


value = 0
plus = 0
ans = 0

for i in range(N-1):
    for j in range(N-i-1):
        value = (A[i]*A[i+j+1]+value) % (1*10**9 + 7)
        

print(value)

### FIXED CODE ###

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

A_sum = sum(A)

value = 0
ans = 0

for i in range(N-1):
    A_sum -= A[i]
    value += A[i]*A_sum

ans = value % (1*10**9+7)

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

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

import fractions
def gcd(list):
    gcd = list[0]
    for a in list:
        gcd = fractions.gcd(gcd, a)
    return gcd

max_gcd = 0
for i in range(n):
    Ai = A.pop(i)
    max_gcd = max(max_gcd, gcd(A))
    A.insert(i, Ai)

print(max_gcd)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
forward = [0]
back =[0]
for i in range(0,n-1):
    forward.append(fractions.gcd(forward[i], a[i]))
    back.append(fractions.gcd(back[i], a[n-i-1]))
ans = 0
for i in range(n):
    ans = max(ans, fractions.gcd(forward[i], back[n-1-i]))
print(ans)
### BUGGY CODE ###

def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 2:
        return add2(l)
    else:
        ys = [x for x in add(n, l[1:])]
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]

    count = len(list(filter(lambda x: x == a, xs)))
    for i in range(2, n+1):
        ys = add(i, xs)
        count += len(list(filter(lambda x: x == a * i, ys)))

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
print(*[sum((a[i:]+a[:i])[::2])-sum((a[i:]+a[:i])[1::2])for i in range(n)])

### FIXED CODE ###

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

# m0 + m1 + m2 + m3 + m4 = d0 + d1 + d2 + d3 + d5
# d0 = (m0 + m1)//2
# d1 = (m1 + m2)//2
# d2 = (m2 + m3)//2
# d3 = (m3 + m4)//2
# d4 = (m4 + m0)//2
# m0 =  d0 - d1 + d2 - d3 + d4
# m1 =  d0 + d1 - d2 + d3 - d4
# m2 = -d0 + d1 + d2 - d3 + d4
# m3 =  d0 - d1 + d2 + d3 - d4
# m4 = -d0 + d1 - d2 + d3 + d4   
s = sum(a)
p = [0 for _ in range(n)]
q = [0 for _ in range(n+1)]
for i in range(n) :
    if i>1 :
        p[i] = p[i-2] + a[i-2]
    q[n-i-2] = q[n-i] + a[n-i-1]

print(*[s-2*p[i]-2*q[i] for i in range(n)])
### BUGGY CODE ###

n,k,*h=map(int,open(0).read().split())
dp = [0]*n
for i in range(1,n):
  dp[i]=min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
H = [int(x) for x in input().split()]
 
def main(N,K,H):
    dp = [0]*N
    for i in range(1,N):
        L = [dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)]
        dp[i] = min(L)
    print(dp[-1])
main(N,K,H)
#自分のコードがTLEになるので、他の人が書いたコードでAC出来るのか確認。
### BUGGY CODE ###

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

import numpy as np

bit_cnt = np.zeros(20, dtype=np.int8)

def get_bit(x):
    bit = np.zeros(20, dtype=np.int8)
    idx = 0
    while x:
        bit[idx] = x % 2
        x //= 2
        idx += 1

    return bit

def sum_patterns(x):
    return x * (x + 1) // 2

l = 0
r = 1
cnt = 0
bit_cnt += get_bit(a[0])
while r != n:
    expand = bit_cnt + get_bit(a[r])
    if all(expand < 2):
        bit_cnt = expand
        r += 1
    else:
        bit_cnt -= get_bit(a[l])
        cnt += r - l
        l += 1

cnt += sum_patterns(r - l)
print(cnt)


### FIXED CODE ###

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

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

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

n = int(input())
suuretu = list(map(int,input().split()))
nn = frg = 0
while nn <= n-2:
    mm = nn+1
    while mm <= n-1:
        if suuretu[nn] == suuretu[mm]:
            frg = 1
            print('NO')
            break
        else:
            mm +=1
    nn += 1
if frg != 1:
    print('YES')

### FIXED CODE ###

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

if len(li) == len(set(li)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**7)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]

def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**6)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]
# 10^6より大きい素因数があったときの処理
re = 1
for k, v in f.items():
  re *= k**v
if m // re != 1:
  idx.append(1)


def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

  
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

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

bridge1 = []
bridge2 = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
    if b == N:
        bridge2.append((a, b))

if len(bridge1) == 0 or len(bridge2) == 0:
    print('IMPOSSIBLE')
    exit()

for b1 in bridge1:
    for b2 in bridge2:
        if b1[1] == b2[0]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

### FIXED CODE ###

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

bridge1 = []
bridge1_right = set()
bridge2 = []
bridge2_left = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
        bridge1_right.add(b)
    if b == N:
        bridge2.append((a, b))
        bridge2_left.add(a)

if len(bridge1) == 0 or len(bridge2) == 0:
    print('IMPOSSIBLE')
    exit()

if len(bridge1_right & bridge2_left) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
  b,c=map(int,input().split())
  for _ in range(b):
    A.append(c)
ans=0
A.sort(reverse=True)
for i in range(N):
  ans+=A[i]
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[]
for i in range(M):
  BC.append(list(map(int,input().split())))
A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)
ans=sum(A)
for i in range(M):
  for _ in range(BC[i][0]):
    if A==[]:
      print(ans)
      exit()
    if A[-1]>BC[i][1]:
      print(ans)
      exit()
    else:
      p=A.pop()
      ans-=p
      ans+=BC[i][1]
      
print(ans)
### BUGGY CODE ###

n = int(input())
ll = [[] for _ in range(n+1)]
for i in range(n):
    ll[0].append(int(input()))

count = 1
for i in range(n):
    ll[count] = ll[0].copy()
    ll[count][count-1] = 0
    max = 0
    for j in ll[count]:
        if j>max:
            max = j
        else:
            pass
    print(max)
    count+=1


### FIXED CODE ###

n = int(input())
ll = [int(input()) for i in range(n)]
llc = ll.copy()
llc.sort()
m1 = llc[n-1]
m2 = llc[n-2]

for l in ll:
    if l == m1:
        print(m2)
    else:
        print(m1)