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

from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(1,m+1):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * (n-1)
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not n in prev: 
                q.append(n)
                prev.append(n)
                siru[n-2] = now
        if not 0 in siru:
            break
    
    
    
    print("Yes")
    print("\n".join(map(str, siru)))
if __name__ == "__main__":
    main()

        

### FIXED CODE ###

from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * n
    siru[0] = 1
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-1]: 
                q.append(n)
                siru[n-1] = now
    
    
    print("Yes")
    print("\n".join(map(str, siru[1:])))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = [0]*(10**5+1)
for i in range(10**5+1):
    index[i] = lsn.count(i)
for l in ls2:
    index[l[1]] = index[l[1]]+index[l[0]]
    index[l[0]] = 0
    sum1 = 0
    for j in range(10**5+1):
        sum1 += j*index[j]
    print(sum1)

### FIXED CODE ###

import collections
N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = collections.Counter(lsn)
sum1 = sum(lsn)
for l in ls2:
    sum1 = sum1 +(l[1]-l[0])*index[l[0]]
    index[l[1]] += index[l[0]]
    index[l[0]] = 0
    print(sum1)
### BUGGY CODE ###

n,m = map(int,input().split())
li = [0]*m
for i in range(m):
  li[i] = list(map(int,input().split()))

ans = 0
for i in range(1,n+1):
  for j in range(m):
    if i < li[j][0] or li[j][1]< i:
      break
  else:
    ans += 1
print(ans)

### FIXED CODE ###

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

lans = 1
rans = n
for i in range(m):
  l,r = map(int,input().split())
  lans = max(lans,l)
  rans = min(rans,r)
if lans <= rans:
  print(len(list(range(lans,rans+1))))
else:
  print(0)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    x3=x2*d
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x3:
                    check[x1]=check[n]+x3
            else:
                check[x1]=check[n]+x3
        else:
            if x1 in check:
                if check[x1]>check[n]+x3+cha:
                    check[x1]=check[n]+x3+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x3+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    x3=x2*d
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x3+cha:
                check[x1]=check[n]+x3+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x3+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
ans = 0

for i in range(N-1):
    B = copy.copy(A)
    del B[:i+1]
    ans += A[i] * sum(B)
    ans = ans % MOD
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
B = copy.copy(A)
C = sum(B)
ans = 0

for i in range(N-1):
    C = (C - B[i]) % MOD
    ans += A[i] * C % MOD
    ans = ans % MOD
print(ans)
### BUGGY CODE ###

from numba import njit

@njit(cache=True)
def f(n):
    #n = 10**9
    ans = 0
    for i,j in zip(range(1,n),range(2,n+1)):
        #print(i,j)
        ans += i%j
    return ans

if __name__ == "__main__":
    n = int(input())
    r = f(n)
    print(r)

### FIXED CODE ###

#n = 10**9
n = int(input())
ans = 0
print(((n-1)*(1+n-1)//2))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
import math
M = max(A)
MOD = 10 ** 9 + 7

bucket = [0] * (M + 1)
for val in A:
    for i in range(2, math.floor(math.sqrt(val)) + 1):
        #print(val, i)
        temp = 0
        while val % i == 0:
            val //= i
            temp += 1
        bucket[i] = max(bucket[i], temp)
    if val != 1:
        bucket[val] = max(bucket[val], 1)
#print(bucket)

L = 1
for n in range(M + 1):
    L *= n ** bucket[n]
#print(L)

ans = 0
for val in A:
    ans = (ans + L // val) % MOD
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import math
M = max(A)
MOD = 10 ** 9 + 7

def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

bucket = [0] * (M + 1)
for val in A:
    for i in range(2, math.floor(math.sqrt(val)) + 1):
        #print(val, i)
        temp = 0
        while val % i == 0:
            val //= i
            temp += 1
        bucket[i] = max(bucket[i], temp)
    if val != 1:
        bucket[val] = max(bucket[val], 1)
#print(bucket)

L = 1
for n in range(M + 1):
    L = (L * n ** bucket[n]) % MOD
#print(L)

ans = 0
for val in A:
    ans = (ans + power_func(val, MOD - 2, MOD))
ans = (ans * L) % MOD
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import fractions as f
n=int(input())
a=list(map(int,input().split()))
cnt=a[0]
for i in range(n):
    cnt=(a[i]*cnt)//f.gcd(a[i],cnt)
ans=0
for i in range(n):
    ans+=cnt//a[i]
    ans=ans%(10**9+7)
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import fractions as f
MOD=10**9+7
fac=[i for i in range(10**6+1)]
inv=[0]*(10**6+1)
inv[1]=1
for i in range(2,10**6+1):
    inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
#print(inv)
MOD=10**9+7
n=int(input())
a=list(map(int,input().split()))
cnt=a[0]
for i in range(n):
    cnt=(a[i]*cnt)//f.gcd(a[i],cnt)
ans=0
cnt=cnt%(10**9+7)
for i in range(n):
    ans+=inv[a[i]]*cnt
    ans=ans%(10**9+7)
    #print(ans)
print(ans)
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

#import numpy as np
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

INF = 10 ** 12

score = [[INF] * W for _ in range(H)]

score[Ch][Cw] = 0

candidates = deque()
candidates.append((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y][x] > s:
            score[y][x] = s
            candidates.appendleft((y, x))
    # warp
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y][x] > s + 1:
            score[y][x] = s + 1
            candidates.append((y, x))

if score[Dh][Dw] == INF:
    print(-1)
else:
    print (score[Dh][Dw])
### BUGGY CODE ###

import numpy as np

N,M,K = map(int,input().split())
A = np.array(input().split(),dtype=int)
B = np.array(input().split(),dtype=int)

AA = np.insert(A,0,0)
BB = np.insert(B,0,0)
AAA = np.cumsum(AA)
BBB = np.cumsum(BB)
max_mins = 0
max_books = 0
for a in enumerate(AAA):
    if a[1] > K:
        break
    for b in enumerate(BBB):
        if a[1] + b[1] > K:
            break
        if a[0] + b[0] > max_books:
            max_books = a[0] + b[0]
print(max_books)            


### FIXED CODE ###

import numpy as np
from bisect import bisect

N,M,K = map(int,input().split())
A = np.array(input().split(),dtype=int)
B = np.array(input().split(),dtype=int)

AA = np.insert(A,0,0)
BB = np.insert(B,0,0)
AAA = np.cumsum(AA)
BBB = np.cumsum(BB)
max_books = 0
for a in enumerate(AAA):
    if a[1] > K:
        break
    books = a[0]
    ind = bisect(BBB,K - a[1])
    books += (ind-1)
    max_books = max(books,max_books)
print(max_books)
### BUGGY CODE ###

from collections import deque
H, W = map(int,input().split())

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.pop()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

n = input()
l = map(int, input().split())
count = 0
while all(i % 2 == 0 for i in l):
      a = [i / 2 for i in l]
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while all(i % 2 == 0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
dd = list(map(int, input().split()))
m = int(input())
tt = list(map(int, input().split()))

for t in tt:
  if dd.count(t) >= tt.count(t):
    continue
  else:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

import collections
n = int(input())
d_list = list(map(int, input().split()))
m = int(input())
t_list = list(map(int, input().split()))

if m > n:
    print("NO")
    exit()

d_c = collections.Counter(d_list)
t_c = collections.Counter(t_list)

for i in t_c:
    if t_c[i] <= d_c[i]:
        continue
    else:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

N = int(input())
ans = 100000
for i in range(1,  10 ** 10):
    if N % i == 0:
        ans = min(ans, max(len(str(i)), len(str(N // i))))

print(ans)


### FIXED CODE ###

N = int(input())
ans = 100000
for i in range(1, 10 ** 5):
    if N % i == 0:
        ans = min(ans, max(len(str(i)), len(str(N // i))))

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

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def get_max(a, b, theta):
    kari = b * math.tan(math.radians(90 - theta))
    if kari > a:
        S = (a * b) - (a * (a * math.tan(math.radians(theta))) / 2)
    else:
        S = (kari * b) / 2
    max_water = S * a
    return max_water




def main():
    a, b, x = map(int, input().split())
    left, right = 0, 90

    for i in range(100000):
        half = (left + right) / 2
        max_water = get_max(a, b, half)
        if max_water >=x:
            left = half
        else:
            right = half

    print(left)





if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def get_max(a, b, theta):
    kari = b * math.tan(math.radians(90 - theta))
    if kari > a:
        S = (a * b) - (a * (a * math.tan(math.radians(theta))) / 2)
    else:
        S = (kari * b) / 2
    max_water = S * a
    return max_water




def main():
    a, b, x = map(int, input().split())
    left, right = 0, 90

    for i in range(10000):
        half = (left + right) / 2
        max_water = get_max(a, b, half)
        if max_water >=x:
            left = half
        else:
            right = half

    print(left)





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

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

Prenum = [[] for i in range(N)]
PreYear = []
PY = [input().split(' ') for i in range(M)]

for i in range(M):
    Pi, Yi = map(int,PY[i])
    Prenum[Pi-1].append(i)

    count = 1
    for i in range(len(Prenum[Pi-1])-1):
        if int(PY[Prenum[Pi-1][i]][1]) > Yi:
            PreYear[Prenum[Pi-1][i]] += 1
        elif int(PY[Prenum[Pi-1][i]][1]) < Yi:
            count +=1 
    PreYear.append(count)

for i in range(M):
    Pi, Yi = map(int,PY[i])
    print('{0:06d}{1:06d}'.format(Pi,PreYear[i]))

### FIXED CODE ###

from operator import itemgetter


N, M = map(int, input().split(' '))
data = []
for i in range(M):
    Pi, Yi = map(int, input().split(' '))
    data.append([i,Pi,Yi])

sorted_data = sorted(data, key=itemgetter(1,2))

codes = []
prev_p = 0
for i,p,y in sorted_data:
    if p!=prev_p:
        x = 1
        prev_p = p
    else:
        x+=1

    code = '{0:06d}{1:06d}'.format(p,x)
    codes.append([i,code])

sorted_codes = sorted(codes, key = itemgetter(0))

for code in sorted_codes:
    print(code[1])
### BUGGY CODE ###

h , w , k = map(int,input().split())
cho = [list(input()) for i in range(h)]
ans = 10**9
for i in range(2**(h-1)):
    cut = [0 for i in range(h)]
    for j in range(h-1):
        if i >> j & 1 == 1:
            cut[j+1] = cut[j]+1
        else:
            cut[j+1] = cut[j]
    maxcut = max(cut)+1
    cou = [0 for i in range(maxcut)]
    ccho = [[0 for i in range(w)] for j in range(maxcut)]
    for j in range(h):
        for l in range(w):
            ccho[cut[j]][l] += int(cho[j][l])
    tyu = maxcut - 1
    hukanou = False
    for j in range(w):
        flag = True
        for l in range(maxcut):
            if cou[l] + ccho[l][j] > k:
                flag = False
                break
        if flag:
            for l in range(maxcut):
                cou[l] += ccho[l][j]
        elif not flag:
            tyu += 1
            for l in range(maxcut):
                if ccho[l][j] > k:
                    hukanou = True
                    break
                cou[l] = ccho[l][j]
        if hukanou:
            break
    if hukanou:
        continue
    ans = min(ans,tyu)
print(ans)

### FIXED CODE ###

h , w , k = map(int,input().split())
cho = [list(input()) for i in range(h)]
ans = 10**9
for i in range(2**(h-1)):
    cut = [0 for i in range(h)]
    for j in range(h-1):
        if i >> j & 1 == 1:
            cut[j+1] = cut[j]+1
        else:
            cut[j+1] = cut[j]
    maxcut = max(cut)+1
    cou = [0 for i in range(maxcut)]
    ccho = [[0 for i in range(w)] for j in range(maxcut)]
    for j in range(h):
        for l in range(w):
            ccho[cut[j]][l] += int(cho[j][l])
    tyu = maxcut - 1
    hukanou = False
    for j in range(w):
        flag = True
        for l in range(maxcut):
            if cou[l] + ccho[l][j] > k:
                flag = False
                break
        if flag:
            for l in range(maxcut):
                cou[l] += ccho[l][j]
        elif not flag:
            tyu += 1
            for l in range(maxcut):
                if ccho[l][j] > k:
                    hukanou = True
                    break
                cou[l] = ccho[l][j]
        if hukanou:
            break
    if hukanou:
        continue
    ans = min(ans,tyu)
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0
length = len(l)
l.sort()

for i in range(length-2):
    for j in range(i+1,length-1):
        for k in reversed(range(j+1,length)):
            if(l[k]<l[i]+l[j]):
                ans += k-j
                break
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
length = len(l)
l.sort()
 
for i in range(n):
    for j in range(i+1,n):
        k = bisect.bisect_left(l,l[i]+l[j])
        ans += max(k - (j+1),0)
print(ans)
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes



for p in get_primes(min(C, 10**6)):
  if p ** 2 > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
INF = 10 ** 17

def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)


### FIXED CODE ###

# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)
### BUGGY CODE ###

K = int(input())

N=7
NotFound = True

for i in range(K):
  if N%K == 0:
    NotFound = False
    print(i+1)
    break
  N=N*10+7

if (NotFound):
  print(-1)

### FIXED CODE ###

K = int(input())

N=7%K
NotFound = True

for i in range(K):
  if N == 0:
    NotFound = False
    print(i+1)
    break
  N=(N*10+7)%K

if (NotFound):
  print(-1)