Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc = sorted(bc, key=lambda x:x[1], reverse=True)
result = 0
for [b,c] in bc:
    if c < a[0]:
        break
    for i in range(b):
        if c < a[i]:
            break
        a[i] = c
    result = result + sum(a[0:b])
    a = a[b:]
print(sum(a)+result)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
N = int(input())
L = list(input().split())
count = 0

for i in range(N-2):
    Li = L[i]
    for j in range(i+1, N-1):
        Lj = L[j]
        for k in range(j+1, N):
            Lk = L[k]
            if (Li == Lj) or (Lj == Lk) or (Lk == Li):
                continue
            else:
                if ((Li + Lj) >= Lk) and ((Li + Lk) >= Lj) and ((Lk + Lj) >= Li):
                    count = count + 1
print(count)

### FIXED CODE ###

A = list(input())

n = A.count('R')
if n != 2:
    print(n)
else:
    m = A.index('S')
    if m == 1:
        print(1)
    else:
        print(2)
if abs(c-a) <= d:
    print('Yes')
elif abs(b-a) <= d and abs(c-b) <= d:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

if abs(c-a) <= d:
    print('Yes')
elif abs(b-a) <= d and abs(c-b) <= d:
    print('Yes')
else:
    print('No')
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]

# Fill 0 mod 3 or not
if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)
# Fill 1 mod 3 or 2 mod 3
else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]

# Fill 0 mod 3 or not
if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)
# Fill 1 mod 3 or 2 mod 3
else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)
n=input()
h=n/3600
s=n%3600
m=s/60
s=s%60
print str(h)+":"+str(m)+":"str(s)

### FIXED CODE ###

S = input()
s = S%60
m = S%3600/60
h = S/3600
print "%d:%d:%d"%(h,m,s)
x,y = map(int,input().split())
x = x % 2019
y = y % 2019
min = 2019
n = y-x
i=0
while(i<n):
  s = (x + i) % 2019
  i = i +1
  if s == 0:
    print(s)
    break
  elif min > s:
    min = s:
min2 = 2019
j=0
while(j<n):
  g = (x + j) % 2019
  j=j+1
  if g == 0:
    break
  elif min2 > g and g != min:
    min2 =g

if min != 0:
  z = (min*min2)%2019
  print(z)


### FIXED CODE ###

l, r = map(int, input().split())

min = 2019

for i in range(l, r+1):
    for j in range(i+1, r+1):
        p = (i % 2019)*(j % 2019) % 2019
        if p < min:
            min = p

        if min == 0:
            print("0")
            exit()

print(min)
while 1:
H , W = map(int, raw_input().split())

if H == 0 and W == 0:
  break
width = ''
for i in range(W):
  width += '#'
for j in range(H):
  print width
    
    

### FIXED CODE ###

while 1:
  h, w = map(int, raw_input().split())
  if h == 0 and w == 0:
    break
  for i in range(h):
    print "#" * w
  print""
#import 
#=input()
#=int(input())
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

la = [a[0]]
lb = [b[0]]
for i in range(1,n):
    la += [a[i]+la[i-1]]
for i in range(1,m):
    lb += [b[i]+lb[i-1]]
j = m - 1
ans = 0
for i in range(n):
    if la[i] > k:
        break
    while lb[j] > k - la[i]:
        j -= 1
    ans = max(ans, i+j+2)
print(ans)

### FIXED CODE ###

#import 
#=input()
#=int(input())
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

la = [0]
lb = [0]
for i in range(n):
    la += [a[i]+la[i]]
for i in range(m):
    lb += [b[i]+lb[i]]
j = m
ans = 0
for i in range(n+1):
    if la[i] > k:
        break
    while lb[j] > k - la[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
import math
N = int(input())
h = list(map(int, input().split()))

dp = list([math.inf for i in range(N + 10)])  # dpテーブル


def recursive(i):
    res = math.inf
    if dp[i] < math.inf:
        return dp[i]

    if i == 0:
        return 0
    res = min(res, recursive(i - 1) + abs(h[i] - h[i - 1]))
    if i > 1:
        res = min(res, recursive(i - 2) + abs(h[i] - h[i - 2]))
    dp[i] = res
    return res


print(recursive(N - 1))


### FIXED CODE ###

import math

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

dp = list([math.inf for i in range(N)])  # dpテーブル
dp[0] = 0
for i in range(N):
    a = dp[i]
    b = dp[i - 1] + abs(h[i] - h[i - 1])
    if a > b:
        dp[i] = b
    else:
        dp[i] = a
    a = dp[i]
    if i > 1:
        b2 = dp[i - 2] + abs(h[i] - h[i - 2])
        if a > b2:
            dp[i] = b2
        else:
            dp[i] = a

print(dp[N - 1])
N = int(input())
h = list(map(int, input().split()))
h.append(0)
count=0
while 1:
  flag=0
  for i in range(N):
    if h[i]>0:
      h[i] -= 1
      flag = 1
      if h[i+1]==0:
        count+=1
      else:
        pass
  if flag==0:
    break
print(count)

### FIXED CODE ###

D = int(input())
print('Christmas' + ' Eve'*(25-D))
n,k =input().split()
K = int(k)
N = int(n)

import math
P = 0
if N < K:
for i in range(1,K):
    P += ((0.5)**(math.ceil( math.log2(float(K/i)) )))/N
else:
    P += (N-K)/N 
    for i in range(K,N+1)
        P += ((0.5)**(math.ceil( math.log2(float(K/i)) )))/N
print(P)

### FIXED CODE ###

n,k =input().split()
K = int(k)
N = int(n)

import math
P = 0
if N < K:
    for i in range(1,N+1):
        P += ((0.5)**(math.ceil( math.log2(float(K/i)) )))/N
else:
    P += (N-K+1)/N 
    for i in range(1,K):
        P += ((0.5)**(math.ceil( math.log2(float(K/i)) )))/N
print(P)
n = int(input())
def Lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else
        return Lucas(n - 1) + Lucas(n - 2)
print(Lucas(n))


### FIXED CODE ###

n = int(input())
L = [0 for i in range(100)]
L[0] = 2
L[1] = 1
def Lucas(n):
    if L[n] != 0:
        return L[n]
    else:
        L[n - 1] = Lucas(n - 1)
        L[n - 2] = Lucas(n - 2)
        return L[n - 1] + L[n - 2]
print(Lucas(n))
""" AtCoder """

import math

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

ans = A[0]

for i in range(1, N):
    ans = math.gcd(ans, A[i])

print(ans)


### FIXED CODE ###

""" AtCoder """

from fractions import gcd

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

ans = A[0]

for i in range(1, N):
    ans = gcd(ans, A[i])

print(ans)
N, M=map(int, input().split())
A=[int(input()) for _ in range(M)]
mod=10**9+7
step=[0]*(N+1)
step[1]=0 if 1 in A else 0
step[2]=0 if 2 in A else 1 if 1 in A else 0
for i in range(3, N+1):
  if i in A:
    continue
  step[i]=(step[i-1]+step[i-2])%mod
print(step[-1])

### FIXED CODE ###

N, M=map(int, input().split())
A=[int(input()) for _ in range(M)]
mod=10**9+7
step=[1]*(N+1)
for a in A:
  step[a]=0
for i in range(2, N+1):
  step[i]=(step[i-1]+step[i-2])%mod*step[i]
print(step[-1])
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())


ten = a//10 + b//10 + c//10 + d//10 + e//10

aa = [a%10,b%10,c%10,d%10,e%10]
zero = aa.count(0)

if zero == 5:
	print(ten)
else:
	for i in range(1,9):
		if  i in aa:
			one = i
			break
	print(ten*10 + (4-zero)*10 +one)

### FIXED CODE ###


a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())


ten = a//10 + b//10 + c//10 + d//10 + e//10

aa = [a%10,b%10,c%10,d%10,e%10]
zero = aa.count(0)

if zero == 5:
	print(ten*10)
else:
	for i in range(1,10):
		if  i in aa:
			one = i
			break
	print(ten*10 + (4-zero)*10 +one)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


def main():
    M = int(input())
    # d = [0] * M
    # c = [0] * M
    digits = []
    # d = sorted(d)

    for i in range(M):
        d, c = list(map(int, input().split()))
        for i in range(c):
            digits.append(d)

    # print(digits)
    ith = 1
    nxt = digits[i] + digits[i+1]
    # print(nxt)
    for i in range(2, len(digits)):
        if nxt + digits[i] >= 10:
            nxt = nxt % 10
            ith += 2
        else:
            nxt = nxt + digits[i]
            ith += 1

    print(ith)


if __name__ == '__main__':
    main()


### FIXED CODE ###

INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


def main():
    M = int(input())
    N = 0
    S = 0

    for i in range(M):
        d, c = list(map(int, input().split()))

        if d == 0 and i == 0:
            continue

        S += d * c
        N += c

    print((N - 1) + (S - 1) // 9)


if __name__ == '__main__':
    main()
s = list(input())
t = list(input())
s = s.sort()
t = t.sort()
t = t.reverse()
s = ''.join(s)
t = ''.join(t)
if s < t :
  print('Yes')
else :
  print('No')

### FIXED CODE ###

s = list(input())
t = list(input())
s.sort()
t.sort()
t.reverse()
s = ''.join(s)
t = ''.join(t)
if s < t:
  print('Yes')
else:
  print('No')
n=int(input())
h=list(map(int,input().split()))
count=0
a=[]
for i in range(1,n):
  if h[i]<=h[i-1]:
    count+=1
    a.append(count)
  else: 
    
    count=0

print(max(a))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
count=0
a=[0]
for i in range(1,n):
  if h[i]<=h[i-1]:
    count+=1
    a.append(count)
  else: 
    
    count=0

print(max(a))
# -*- coding: utf-8 -*-
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))
Cn = list(map(int, input().split()))

An.sort()
Bn.sort()
Cn.sort()

# print(An)
# print(Bn)
# print(Cn)

# B
C_cnt = []
C_sum = 0
j = 0
for i in range(N):
    while j < N:
        if Bn[i] < Cn[j]:
            C_cnt.append(N - j)
            C_sum += N - j
            break
        else:
            j += 1

B_cnt = []
temp_sum = 0
for cnt in C_cnt:
    B_cnt.append(C_sum - temp_sum)
    temp_sum += cnt

A_cnt = 0
j = 0
for i in range(N):
    while j < N:
        if An[i] < Bn[j]:
            A_cnt += B_cnt[j]
            break
        else:
            j += 1

# print(C_cnt)
# print(B_cnt)
print(A_cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))
Cn = list(map(int, input().split()))

An.sort()
Bn.sort()
Cn.sort()

# print(An)
# print(Bn)
# print(Cn)

# B
C_cnt = []
C_sum = 0
j = 0
for i in range(N):
    while j < N:
        if Bn[i] < Cn[j]:
            C_cnt.append(N - j)
            C_sum += N - j
            break
        else:
            j += 1


B_cnt = []
temp_sum = 0
for cnt in C_cnt:
    B_cnt.append(C_sum - temp_sum)
    temp_sum += cnt

A_cnt = 0
j = 0
for i in range(N):
    while j < N:
        if An[i] < Bn[j]:
            if j < len(B_cnt):
                A_cnt += B_cnt[j]
            break
        else:
            j += 1

# print(C_cnt)
# print(B_cnt)
print(A_cnt)
from math import frexp
  a, b = map(int, input().split())
  print(frexp(b)[1]-frexp(a)[1]+1)

### FIXED CODE ###

x, y = list(map(int, input().split()))
a = x
ans = 0
while a <= y:
    a = a << 1
    ans += 1
print(ans)
import sys
sys.setrecursionlimit(10**9+7)
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(M)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 
print(ans)


### FIXED CODE ###

def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(N)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

print(ans)
n=0
while i = input() != "0":
    n++
    print("Case " + str(n) + ":" +i)


### FIXED CODE ###

n=0
i = int(input())
while i != 0:
    n+=1
    print("Case " + str(n) + ": " +str(i))
    i = int(input())
import bisect
n=int(input())
li=[111,222,333,444,555,666,777,888]

print(li[bisect.bisect_left(li,n)])

### FIXED CODE ###

import bisect
n=int(input())
li=[111,222,333,444,555,666,777,888]

a=bisect.bisect_left(li,n)

print((a+1)*111)
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

assert len(h) == N, print(f'length of steps {len(h)} doesn\'t equal to {K}')

# list dp retains information for the minimum costs
# if dp[i] = n, it means n is the minimum cost to get to i step
# if dp[i] = INF, it means the minimum cost has not been evaluated yet
INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

for i in range(N):
    for j in range(1, min(K+1, len(h)-i)):
        dp[i+j] = min(dp[i] + abs(h[j+i] - h[i]), dp[i+j])
        
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

for i in range(N):
    for j in range(1, min(K+1, len(h)-i)):
        dp[i+j] = min(dp[i] + abs(h[j+i] - h[i]), dp[i+j])

print(dp[N-1])
import sys
for e in sys.stdin:
 p,q,r,s,t,u,x,y=map(float,e.split())
 a=((x-p)*(u-q)-(y-q)*(t-p))/((r-p)*(u-q)-(s-q)*(t-p))
 b=(x-p-a*(r-p))/(t-p)
 print(['NO','YES'][0<a<1-b and 0<b<1-a])


### FIXED CODE ###

import sys
def f(a,b,c,d):z=(c-a)*(y-d)-(d-b)*(x-c);return[-1*(z==0),1][z>0]
for e in sys.stdin:
 p,q,r,s,t,u,x,y=map(float,e.split())
 print(['NO','YES'][f(p,q,r,s)==f(r,s,t,u)==f(t,u,p,q)])
N, M, K = map(int, input().split())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
def solve(A, N, B, M, K):
  
  def cumsum(l):
    rt = [0]
    s = 0
    for n in l:
      s += n
      rt.append(s)
    return rt
  
  preA = cumsum(A)
  preB = cumsum(B)
  
  total = N + M
  s, e = 0, total
  
  def can_read(num):
    for i in range(N + 1):
      j = num - i
      if j < (M + 1) and (preA[i] + preB[j]) <= K:
      	return True
    return False

  res = 0
  while s <= e:
    mid = s + (e - s) // 2
    can = can_read(mid)
    
    if can:
      res = mid
      s = mid + 1
    else:
      e = mid - 1
  
  return res

res = solve(A, N, B, M, K)
print(res)

### FIXED CODE ###

N, M, K = map(int, input().split())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
def solve(A, N, B, M, K):
  
  def cumsum(l):
    rt = [0]
    s = 0
    for n in l:
      s += n
      rt.append(s)
    return rt
  
  preA = cumsum(A)
  preB = cumsum(B)
  
  s, e = 0, N + M
  
  def can_read(num):
    for i in range(N + 1):
      j = num - i
      if j >= 0 and j < (M + 1) and (preA[i] + preB[j]) <= K:
      	return True
    return False

  res = 0
  while s <= e:
    mid = s + (e - s) // 2
    can = can_read(mid)
    
    if can:
      res = mid
      s = mid + 1
    else:
      e = mid - 1
  
  return res

res = solve(A, N, B, M, K)

print(res)
def solve():
    n = int(input())
    s = []
    for i in range(n):
        s.append(int(input()))

    s.sort()
    score = sum(s)

    i = 0
    flag = True
    if not score % 10:
        if n == 1:
            flag = False
        while 1:
            if s[i] % 10:
                score -= s[i]
                break
            i += 1
            if i == n - 1:
                flag = False
                break

    if flag:
        print(score)
    else:
        print(0)


solve()

### FIXED CODE ###

def solve():
    n = int(input())
    s = []
    for i in range(n):
        s.append(int(input()))

    s.sort()
    score = sum(s)

    i = 0
    flag = True
    if not score % 10 and n != 1:
        while 1:
            if s[i] % 10:
                score -= s[i]
                break
            i += 1
            if i == n - 1:
                flag = False
                break
    elif not score % 10 and n == 1:
        flag = False

    if flag:
        print(score)
    else:
        print(0)


solve()
import numpy as np
N = int(input())
S = [input() for __ in range(N)]

S = np.array(S)
keys = set(S)
ans = {}
cnt = 0
ls = []
for key in keys:
    ans[key] = len(np.where(S == key)[0])

max_v = max(ans.values())
keys = [k for k, v in d.items() if v == max_v]
keys.sort()
for key in keys:
    print(key)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
    S = input()
    if S in d.keys():
        d[S] = d[S] + 1
    else:
        d[S] = 1
max_val = max(d.values())
max_k_ls = [kv[0] for kv in d.items() if kv[1]==max_val]
max_k_ls = sorted(max_k_ls)

print(*max_k_ls, sep="\n")
ans = 10**12
n = int(input())
for a in range(1,int(math.sqrt(N)):
  for b in range(1,int(math.sqrt(N)):
    if a * b == n:
      ans_n = a + b -2
      if ans > ans_n:
        ans = ans_n
print(ans) 

### FIXED CODE ###

n = int(input())
ans = float('inf')
 
for i in range(1, 10**6+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)
 
print(ans-2)
s=list[input()]
if s[2]==s[3] and s[4]==s[5]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=list(input())
if s[2]==s[3] and s[4]==s[5]:
  print("Yes")
else:
  print("No")
n,a,b =map(int,input().split())
c = a+b

sum1 = n//c
l = n%c
if a>l:
  sum2 = l
else:
  sum2 = a
  
print(sum1+sum2)

### FIXED CODE ###

a,b,c=input()
if a==b and b==c:
  print("No")
else:
  print("Yes")
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x)[1]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i] + 2*d == a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break

### FIXED CODE ###

while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x))[-1]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i+1] + d != a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# # print(f)
# for i in range(N):
#     x = D[F.root(i)]
#     ret = len(x)
#     ret -= 1
#     ret -= len(x & f[i])
#     ret -= len(x & B[i])
#     ans[i] = ret
print(*ans)


### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.getCount(i) - 1 for i in range(N)]
# print(ans)
# print(G.count)
for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in CD:
    if G.same(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)
print "\n".join(sorted([input() for x in xrange(10)])[:3])

### FIXED CODE ###

print "\n".join(map(str,sorted([input() for _ in xrange(10)], reverse = True)[:3]))