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

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

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

# N本 まで使うか 10^4
dp=[0] * (N+1)

cost =[0, 2,5,5,4,5,6,3,7,6]

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める、数値のままであとでやる。とりあえずpypy
        d = len(str(dp[i])) if dp[i] else 0
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)


print(dp[N])

### FIXED CODE ###

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

# 0初期化ではダメ。組合せ不可を表し、演算しても問題ない状態にしておく
dp=[-float("inf")] * (N+1)
dp[0]=0

cost =[0, 2,5,5,4,5,6,3,7,6]
for i in range(N+1):
    for a in A:
      # -inf初期化なので、不可能なものの演算結果も同じ
       new_i = i + cost[a]
       if new_i <= N:
        dp[new_i] = max([dp[new_i],  dp[i]+1])

sa = sorted(A, reverse=True)
n = N
ans = 0
while n > 0:
  for a in sa:
    nn = n-cost[a]
    if nn >= 0 and dp[n] == dp[nn] +1:
      ans = ans * 10 + a
      n -= cost[a]
      break

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

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())

PATH = [[] for _ in range(N + 1)]

for _ in range(N-1):
    a, b = map(int, readline().split())
    PATH[a].append(b)
    PATH[b].append(a)

POINT = [0] * (N + 1)

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


ans = [0] * (N+1)

STATE = [False] * (N+1)


def dfs(s, plus):
    p = POINT[s]
    pt = p + plus
    ans[s] += pt

    STATE[s] = True

    for v in PATH[s]:
        if STATE[v]:
            continue
        dfs(v, pt)


dfs(1, 0)
print(" ".join(map(str, ans[1:])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())

PATH = [[] for _ in range(N + 1)]

for _ in range(N-1):
    a, b = map(int, readline().split())
    PATH[a].append(b)
    PATH[b].append(a)

POINT = [0] * (N + 1)

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


ans = [0] * (N+1)

STATE = [False] * (N+1)


def dfs(s, plus):
    p = POINT[s]
    pt = p + plus
    ans[s] += pt

    STATE[s] = True

    for v in PATH[s]:
        if STATE[v]:
            continue
        dfs(v, pt)


dfs(1, 0)
print(" ".join(map(str, ans[1:])))
### BUGGY CODE ###

def maxElem( lis ):
  '''
  与えられたリストの中に、最も多く存在する要素を返す
  (最大の数の要素が複数ある場合、pythonのsetで先頭により近い要素を返す)
  '''
  L = lis[:]#copy
  S = set(lis)
  S = list(S)
  MaxCount=0
  ret='nothing...'

  for elem in S:
    c=0
    while elem in L:
      ind = L.index(elem)
      foo = L.pop(ind)
      c+=1
    if c>MaxCount:
      MaxCount=c
      ret = elem
  return ret


if __name__ == "__main__" :
    n = int(input())
    array = list(map(int, input().split()))

    for i in range(0, n):
        array[i] = array[i] - (i + 1)
    elem = int(maxElem(array))
    
    for i in range(0, n):
        array[i] = abs(array[i] - elem)

    sum_n = sum(array)

    print(sum_n)

### FIXED CODE ###

import collections
from statistics import median

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

for i in range(0, n):
    array[i] = array[i] - (i + 1)
c = collections.Counter(array)
elem = int(c.most_common()[0][0])

# print(c.most_common()[0][0])
# print(array)
# print(elem)
# if c.most_common()[0][1] != 1:
#     # print("test")
#     for j in range(0, n):
#         array[j] = abs(array[j] - elem)
# else:
#     for j in range(0, n):
#         array[j] = abs(array[j])
b = int(median(array))
for j in range(0, n):
    array[j] = int(abs(array[j] - b))

print(sum(array))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for j in range(N):
    original = "RGB"
    if S[j] in original:
        for i in range(j):
            obj = original.replace(S[j], "")
            if S[i] in obj:
                for k in range(j+1, N):
                    obj_2 = obj.replace(S[i], "")
                    if S[k] == obj_2:
                      	if (j-i) != (k-j):
                        	ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()

r = S.count("R")
g = S.count("G")
b = S.count("B")

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cnt += 1

print(r*g*b - cnt)
### BUGGY CODE ###

#入力
N = int(input())
li = list(map(int,input().split()))

S = 0
for i in range(N):
    S = S + li.index(li[i])

if S == N*(N-1)/2:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

N = int(input())
li = list(map(int, input().split()))
li.sort()


S = 1
for i in range(N-1):
    if  li[i+1] == li[i]:
        S = S*0
    else:
        S = S
if S == 0:
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())

all_str = []
for i in range(N):
    str_temp = input()
    all_str.append(str_temp)

unique_str = (list(set(all_str)))
unique_str.sort()
max_cnt = 0
str_num = dict()
for i in unique_str:
    cnt = all_str.count(i)
    str_num[i] = cnt
    if max_cnt < cnt:
        max_cnt = cnt

disp_list = []
for i in str_num:
    current_cnt = str_num[i]
    if current_cnt == max_cnt:    
        disp_list.append(i)
    

for i in disp_list:
    print(i)
    

    


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

N = int(input())

all_str = []
for i in range(N):
    str_temp = input()
    all_str.append(str_temp)
all_str.sort()
coll_str = (collections.Counter(all_str))
count_max = 0
j = 0
max_str = coll_str.most_common()
for i in max_str:
    
    num_of_str =  i[1]
    if num_of_str == count_max or j == 0:
        print(i[0])
        j = 1
        count_max = num_of_str
        
    if num_of_str < count_max:
        break
### BUGGY CODE ###

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

hyoukou = list(map(int,input().split()))

roadssta = []
roadsfin = []

for i in range(m):
    base = input().split()
    roadssta.append(int(base[0]))
    roadsfin.append(int(base[1]))

ans = 0

ten = 1

for i in hyoukou:

    if ten not in roadssta and ten not in roadsfin:
        ans += 1
        ten += 1
        continue
    
    else:
        access = [0]
        stacnt = 0
        fincnt = 0
        
        for s in roadssta:
            if s == ten:
                access.append(hyoukou[roadsfin[stacnt]-1])
                stacnt += 1
            else:
                stacnt += 1
        
        for k in roadsfin:
            if k == ten:
                access.append(hyoukou[roadssta[fincnt]-1])
                fincnt += 1
            else:
                fincnt += 1

        if i>max(access):
            ans += 1
            ten += 1
        else:
            ten += 1

print(ans)

### FIXED CODE ###

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

hyoukou = list(map(int,input().split()))

roadssta = []
roadsfin = []

ten = [1]*n

for i in range(m):
    base = input().split()
    a = int(base[0])
    b = int(base[1])
    if hyoukou[a-1]>hyoukou[b-1]:
        ten[b-1] = 0
    elif hyoukou[a-1]<hyoukou[b-1]:
        ten[a-1] = 0
    else:
        ten[a-1] = 0
        ten[b-1] = 0

print(ten.count(1))
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
c=-(10**18)
for x in range(1,N+1):
    c=max(c,main(x))
print(c)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main2(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(A*x//B-A*(x//B))

if N>=B-1:
    Z=B-1
else:
    Z=N
print((main2(Z)))

#print(C)
### BUGGY CODE ###

N, K = map( int, input().split() )
x = list( map( int, input().split() ))

'''
x = sorted( x, key = lambda x: abs(x) )[ : K ]
x.sort()

m, M = x[ 0 ], x[ - 1 ]
print( abs( M - m ) + min( abs( m ), abs( M ) ))
'''

ret = 10 ** 18
for i in range( N - K + 1 ):
  s = x[ i: K + i ]
  l, r = s[0], s[ -1 ]
  ret = min( ret, abs( l - r ) + min( abs( r ), abs( l ) ) )
print( ret )

### FIXED CODE ###

N, K = map( int, input().split() )
x = list( map( int, input().split() ))
 
ret = 10 ** 18
for i in range( N - K + 1 ):
  l, r = x[i], x[ K + i - 1 ]
  ret = min( ret, abs( l - r ) + min( abs( r ), abs( l ) ) )
print( ret )
### BUGGY CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    count = 0
    for i in range(n):
        flg = True
        for j in range(i):
            if p[i] > p[j]:
                flg = False
        if flg:
            count += 1

    print(count)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    count = 0
    min_num = n+1
    for i in p:
        if i < min_num:
            min_num = i
            count += 1
    print(count)


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

N = int(input())
S = list(input())

nW = 0
nE = 0

for i in range(N):
    if S[i] == 'E':
        nE += 1
    else:
        nW += 1

count = N

for i in range(N):
    if S[i] == 'E':
        temp = 1
    else: 
        temp = 0
    tempW = 0
    tempE = 0
    for j in range(i):
        if S[j] == 'W':
            tempW += 1
        else:
            tempE += 1
    if tempW + nE - tempE - temp < count:
        count = tempW + nE - tempE - temp

print(count)

### FIXED CODE ###

import math
import numpy as np

N = int(input())
S = list(input())

nW = [0 for i in range(N)] #iまでのWの数
nE = [0 for i in range(N)] #iまでのEの数

if S[0] == 'W':
    nW[0] = 1
else:
    nE[0] = 1

for i in range(1, N):
    if S[i] == 'W':
        nW[i] = nW[i-1] + 1
        nE[i] = nE[i-1]
    else:
        nW[i] = nW[i-1]
        nE[i] = nE[i-1] + 1

if nE[N-1] - nE[0] < nW[N-1]:
    count = nE[N-1] - nE[0]
else:
    count = nW[N-1]

for i in range(1,N-1):
    if nW[i-1] + nE[N-1] - nE[i] < count:
        count = nW[i-1] + nE[N-1] - nE[i]

print(count)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dist = [[float('inf')] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            queue = deque([(i, j)])
            while queue:
                a, b = queue.popleft()
                for da, db in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    na, nb = a + da, b + db
                    if 0 <= na < H and 0 <= nb < W and A[na][nb] == '.' and dist[na][nb] > dist[a][b] + 1:
                        dist[na][nb] = dist[a][b] + 1
                        queue.append((na, nb))
print(max(max(row) for row in dist))

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dp = [[float('inf') if A[i][j] == '.' else 0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H):
    for j in range(W)[::-1]:
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H)[::-1]:
    for j in range(W):
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
print(max(max(row) for row in dp))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1

for i in range (1,N):
  if P[i] == min(P[0:i+1]):
    ans = ans + 1
print(ans)
  

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1
P0 = P[0]

for i in range (1,N):
  if P[i] <= P0:
    ans = ans + 1
    P0 = P[i]
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

Al = sorted(A,reverse=True)[:K]
Bl = sorted(B,reverse=True)[:K]
Cl = sorted(C,reverse=True)[:K]

result = []
for a in Al:
    for b in Bl:
        for c in Cl:
            result.append(a+b+c)

result.sort(reverse=True)

for i in range(K):
    print(result[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
button = [0]*n
button1 = a[0] - 1
count = 1
while True:
    button[button1] += 1
    button1 = a[button1] - 1
    if button[1] == 1:
        print(count)
        break
    try:
        button.remove(2)
        print('-1')
        break
    except:
        count += 1
        pass

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
now = a[0]
c = 1

if now == 2:
    print(1)
    exit()

for i in range(n):
    now = a[now-1]
    c += 1
    if now == 2:
        print(c)
        exit()
print(-1)
### BUGGY CODE ###

from sys import stdin
K, S = map(int, stdin.readline().rstrip().split())
l = list(i for i in range(K+1))
def binary_search(list, item):
    count = 0
    low = 0
    high = len(list) - 1
    while low <= high:
        if (low + high) % 2 == 0:
            mid = (low + high) // 2
        else:
            mid = (low + high) // 2 - 1
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None
count = 0
for i in range(K+1):
    for j in range(K+1):
        if binary_search(l, S - i - j):
            count += 1
print(count)
            


### FIXED CODE ###

from sys import stdin
K, S = map(int, stdin.readline().rstrip().split())
l = list(i for i in range(K+1))
count = 0
for i in range(K+1):
    for j in range(K+1):
        z = S - i - j
        if 0 <= z <= K:
            count += 1
print(count)
### BUGGY CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*10**i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i += 1

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)


### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

P=[]
for i in A: P.append(T[i-1])

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a,match_cnt in P:
		if 0<=i-match_cnt:
			dp_src=dp[i-match_cnt]  #dpの遷移元
			if dp_src is not None:
				if dp[i] is None:
					dp[i]=dp_src+str(a)
				else:
					if int(dp[i])<int( dp_src+str(a) ):
						dp[i]=dp_src+str(a)	
print dp[N]


### FIXED CODE ###

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]
### BUGGY CODE ###

from copy import deepcopy
from collections import defaultdict

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = defaultdict(list)
for r, c, v in rcv:
    d[r].append([c, v])

for r in d.keys():
    d[r].sort()

dp = [0] * (C + 1)

for r, li in sorted(d.items()):
    prev = deepcopy(dp)
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[cg] = max(dp[cg], prev[cs] + val)
            mx = max(mx, vg)

        dp[cs] = max(dp[cs], prev[cs] + vs)

    for c in range(C):
        dp[c+1] = max(dp[c+1], dp[c])

ans = dp[C]
print(ans)


### FIXED CODE ###

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

board = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in rcv:
    board[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        v = board[r][c]
        for i in range(4):
            dp[0][r][c] = max(dp[0][r][c], dp[i][r-1][c])
            dp[1][r][c] = max(dp[1][r][c], dp[i][r-1][c] + v)

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

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

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(N+1)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    for j in range(N//2,0,-1):
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i-1])

print(dp[N][N//2])



### FIXED CODE ###

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])
### BUGGY CODE ###

import math

n = int(input())


sosu = set([2])
tansaku = set(range(3,n+1))
kari = set(tansaku)

while math.sqrt(n) > max(sosu):
    for var in tansaku:
        if var % max(sosu) == 0:
            kari.discard(var)
    tansaku = set(kari)
    sosu.add(min(tansaku))
sosu = sosu | tansaku

i = 1
j = 0
kari = set(sosu)

while n != 1:
    for var in sosu:
        if n % (var ** i) == 0:
            n = n / (var ** i)
            j += 1
        else:
            kari.discard(var)
    sosu = set(kari)

    i += 1
    if i > 1000:
        break

print(j)

### FIXED CODE ###

import math
import sys

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())

if n <= 1:
    print(0)
    sys.exit()

yakusu = set(make_divisors(n))
yakusu.discard(1)

sosu = set([min(yakusu)])
tansaku = set(yakusu)
kari = set(tansaku)



while 1:
    for var in tansaku:
        if var % max(sosu) == 0:
            kari.discard(var)
    tansaku = set(kari)
    if len(tansaku) == 0:
        break
    sosu.add(min(tansaku))
sosu = sosu | tansaku

i = 1
j = 0
kari = set(sosu)

while n != 1:
    for var in sosu:
        if n % (var ** i) == 0:
            n = n / (var ** i)
            j += 1
        else:
            kari.discard(var)
    sosu = set(kari)

    i += 1
    if i > 1000:
        break

print(j)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from queue import *


class Edge(object):
    def __init__(self, dst, len_):
        self.dst = dst
        self.len = len_


MAX_K = int(1e5 + 5)
INF = int(1e9)

K = 0
dis = [INF for i in range(0, MAX_K)]
vis = [False for i in range(0, MAX_K)]
edge = [[] for i in range(0, MAX_K)]
q = Queue()


def add(s, t, d):
    edge[s].append(Edge(t, d))


def build():
    for i in range(1, K):
        add(i, i * 10 % K, 0)
        add(i, (i + 1) % K, 1)


def spfa(s):
    dis[s] = 0
    q.put(s)
    while not q.empty():
        x = q.get()
        vis[x] = False
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                if not vis[e.dst]:
                    q.put(e.dst)
                    vis[e.dst] = True


if __name__ == "__main__":
    K = int(input())
    build()
    spfa(1)
    print(dis[0] + 1)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from queue import *


class Edge(object):
    def __init__(self, dst, len_):
        self.dst = dst
        self.len = len_


MAX_K = int(1e5 + 5)
INF = int(1e9)

K = 0
dis = [INF for i in range(0, MAX_K)]
vis = [False for i in range(0, MAX_K)]
edge = [[] for i in range(0, MAX_K)]
q = PriorityQueue()


def add(s, t, d):
    edge[s].append(Edge(t, d))


def build():
    for i in range(1, K):
        add(i, i * 10 % K, 0)
        add(i, (i + 1) % K, 1)


def dij(s):
    dis[s] = 0
    q.put((0, s))
    while not q.empty():
        x = q.get()[1]
        if vis[x]:
            continue
        vis[x] = True
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                q.put((dis[e.dst], e.dst))


if __name__ == "__main__":
    K = int(input())
    build()
    dij(1)
    print(dis[0] + 1)