Harryxun/stf_run huggingface dataset:
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  e = maths = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')


### FIXED CODE ###

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
n = int(input())
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  u = set()
  i = None
  for x in a:
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if len(a) == n:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')
from _collections import deque
n,m,k=map(int,input().split())

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

def s(z,y):
    if x[y]>0:
        return
    x[y]=z
    for i in fre[y]:
        if x[i]==-1:
            s(z,i)

for i in range(1,n+1):
    s(i,i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))



### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x


fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]
for i in range(1,n+1):
    anser=-root[r(i)]-1
    anser-=len(fre[i])
    for j in bro[i]:
        if r(i)==r(j):
            anser-=1
    ans.append(str(anser))
print(" ".join(ans))
from collections import deque

N, M, K = map(int, input().split())
A = deque([int(x) for x in input().split()])
B = deque([int(x) for x in input().split()])
tsundoku = 0

while K > 0:
    if not A:
        K -= B.popleft()
    elif not B:
        K -= A.popleft()
    elif A[0] < B[0]:
        K -= A.popleft()
    elif A[0] > B[0]:
        K -= B.popleft()
    elif A[0] == A[0]:
        if A[1] < B[1]:
            K -= A.popleft()
        elif A[1] > B[1]:
            K -= B.popleft()

    if K >= 0:
        tsundoku += 1

print(tsundoku)


### FIXED CODE ###

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


def cusum(array):
    for i in range(len(array) - 1):
        array[i + 1] += array[i]


cusum(A)
cusum(B)
A = [0] + A
B = [0] + B
tsundoku = 0
ia = 0
ib = M

for ia in range(N + 1):
    if A[ia] > K:
        break
    while A[ia] + B[ib] > K and ib >= 0:
        ib -= 1
    tsundoku = max(ia + ib, tsundoku)

print(tsundoku)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(0)
  exit(0)
if M == 0 and (N > 2):
  print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
d = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
for i in range(N):
  d[uf.Find_Root(i)].append(a[i])
res = 0
x = []
y = 0
for i in range(N):
  d[i].sort(reverse = True)
  if len(d[i]):
    res += d[i].pop()
    y += 1
  x += d[i]
x.sort()
for i in range((y - 1) * 2 - y):
  if i > len(x):
    print("Impossible")
    exit(0)
  res += x[i]
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(0)
  exit(0)
if M == 0 and (N > 2):
  print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
d = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
for i in range(N):
  d[uf.Find_Root(i)].append(a[i])
res = 0
x = []
y = 0
for i in range(N):
  d[i].sort(reverse = True)
  if len(d[i]):
    res += d[i].pop()
    y += 1
  x += d[i]
if y == 1:
  print(0)
  exit(0)
x.sort()
for i in range((y - 1) * 2 - y):
  if i >= len(x):
    print("Impossible")
    exit(0)
  res += x[i]
print(res)
import math
import fractions
import sys

sys.setrecursionlimit(10**8)
a,b = [int(x) for x in input().split()]
x = fractions.gcd(a,b)

is_prime = [1]*(x+1)
is_prime[0] = 0
is_prime[1] = 0
ans = 1
for i in range(2,x+1):
    if is_prime[i]:
        if x%i==0:
            ans += 1
        for j in range(2*i,x+1,i):
            is_prime[j] = 0
print(ans)

### FIXED CODE ###

from fractions import gcd

a,b = [int(x) for x in input().split()]

def prime_factor(n):
    x = int(n**0.5)
    res = [1]
    for i in range(2,x+1):
        if n%i==0:
            while n%i==0:
                n //= i
            res.append(i)
    if n!=1:
        res.append(n)
    return res

z = gcd(a,b)
print(len(prime_factor(z)))
n,a,b = map(int,input().split())

mod = 10**9+7

all_combi = pow(2,n,mod)




p = 1
q = 1

for i in range(b):
    
    p *= n-i
    p %= mod
    q *= i+1
    q %= mod
    
    if i==a-1:
        nca = p * pow(q,-1,mod) % mod
        
    if i==b-1:
        ncb = p * pow(q,-1,mod) % mod

        
ans = all_combi -nca -ncb -1
ans %= (10**9+7)
    
print(ans)

### FIXED CODE ###

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

mod = 10**9+7

all_combi = pow(2,n,mod)




p = 1
q = 1

for i in range(b):
    
    p *= n-i
    p %= mod
    q *= i+1
    q %= mod
    
    if i==a-1:
        nca = p * pow(q,mod-2,mod) % mod
        
    if i==b-1:
        ncb = p * pow(q,mod-2,mod) % mod

        
ans = all_combi -nca -ncb -1
ans %= (10**9+7)
    
print(ans)
import sympy

N = 3
Y = list(map(int,input().split(' ')))


symbols = []
for i in range(N):
    symbols.append(sympy.Symbol('x' + str(i)))

equation = []
for i in range(N):
    i1 = i
    i2 = i + 1 
    if i2 >= N:
        i2 = 0
    equation.append(0.5*symbols[i1] + 0.5*symbols[i2] - Y[i])

for i in range(N):
    print(str(int(sympy.solve(equation)[symbols[i]])) + " " , end="")
print()

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
N = int(input())
A = list(map(int, input().split()))
s = sum(A)
r = [s - 2 * sum(A[1::2])]

for i in range(N-1):
    r.append(2 * A[i] - r[i])
    
r = map(str, r)
print(" ".join(r))

'''
5
3 8 7 5 5
'''
s = input()
t = input()
l = 10**5
S = s*l

a = 0
flag = True
for i in range(len(t)):
    if t[i] in S[a:]:
        a += S[a:].find(t[i])+1
    else:
        flag = False
        break
        
if flag:
    print(a)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()
s_ = s[:]
cnt = 0
tlen = len(t)
ans = 0
flag = True

while cnt < tlen:
    
    num = s_.find(t[cnt])
    
    if num != -1:
        ans += (num+1)
        s_ = s_[(num+1):]
        cnt += 1
        flag = False
    else:
        if flag:
            print(-1)
            exit(0)
        ans += len(s_)
        s_ = s[:]
        flag = True
        
print(ans)
import re

i = input().split()[1]
s = input()
k = 0
result = []

while k < i:
    ft, et = [int(n) for n in input().split()]
    result.append(len(re.findall("AC", s[ft - 1:et])))
    k += 1

for kekka in result:
    print(kekka)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
s = input()

count = [0]
for i in range(1, n):
    count.append(count[i-1])
    if(s[i-1:i+1] == "AC"):
        count[i] += 1

# print(count)

for _ in range(q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])
class UnionFind():
  def __init__(self,n):
    self.parents = list(range(n))
    self.size = [1]*n
  
  def find(self,x):
    if self.parents[x] == x:
      return x
	
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.size[x]>self.size[y]:
      x,y=y,x
	
    self.size[x]+=self.size[y]
    self.parents[y] = x
  
  def sizeofset(self,x):
    return self.size[self.find(x)]


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

cnt=(N)*(N-1)//2
L=[[int(x) for x in input().split()] for _ in range(M)]
ans=[]

for a,b in L[::-1]:
  ans.append(cnt)
  if uf.find(a)!=uf.find(b):
    cnt-= uf.sizeofset(a)*uf.sizeofset(b)
    uf.union(a,b)

for x in ans[::-1]:
  print(x)

### FIXED CODE ###

class UnionFind():
  def __init__(self,n):
    self.parents = list(range(n))
    self.size = [1]*n
  
  def find(self,x):
    if self.parents[x] == x:
      return x
	
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.size[x]<self.size[y]:
      x,y=y,x
	
    self.size[x]+=self.size[y]
    self.parents[y] = x
  
  def same(self,x,y):
    return self.find(x) == self.find(y)
  
  def sizeofset(self,x):
    return self.size[self.find(x)]


N,M=map(int,input().split())
uf = UnionFind(N+1)

cnt=(N)*(N-1)//2
L=[[int(x) for x in input().split()] for _ in range(M)]
ans=[]

for a,b in L[::-1]:
  ans.append(cnt)
  if not uf.same(a,b):
    cnt -= uf.sizeofset(a)*uf.sizeofset(b)
    uf.union(a,b)

for x in ans[::-1]:
  print(x)
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N)] for i in range(N)] 
for x,y,z in edges:
    graph[x-1][y-1] = z
    graph[y-1][x-1] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a-1][b-1]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

### FIXED CODE ###

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

Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x,y = map(int, input().split())
    XY.append((x,y))
    
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, K)
#print(shortest)

questions = XY

for x,y in questions:
    ans = shortest[x] + shortest[y]
    print(ans)
n,x=map(int,input().split())
xlist=list(map(int,input().split()))
xlist.sort(key=lambda xx:abs(xx-x))
m=abs(xlist[0]-x)
for i in range(n):
    xlist[i]-=x
    xlist[i]=abs[xlist[i]]
while xlist==[0]*n:
   for i in range(n):
        xlist[i]%=m
        if xlist[i]>0:
            m=min((m,xlist[i]))
print(m)

### FIXED CODE ###

def gcd(x,y):
    while x%y:
        x%=y
        x,y=(y,x)
    return y
n,x=map(int,input().split())
xlist=list(map(int,input().split()))
xlist.sort(key=lambda xx:abs(xx-x))
for i in range(n):
    xlist[i]-=x
    xlist[i]=abs(xlist[i])
m=xlist[-1]
while xlist!=[0]*n:
    for i in range(n):
        
        xlist[i]%=m
        if xlist[i]>0:
            m=gcd(m,xlist[i])
print(m)
import math
a, b = map(int,input().split())
gcd = math.gcd(a,b)
lcm = (a*b)//gcd
print(lcm)

### FIXED CODE ###

a, b = map(int,input().split())
for i in range(1,b+1):
  if (a*i) % b == 0:
    print(a*i)
    break
N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*(1+N+max(a)+1)

for i in range(N):
  w.append(1+i+a[i])
  s.append(1+i-a[i])
  num[1+i-a[i]]+=1
for i in range(N):
  count+=num[w[i]]
print(count)

### FIXED CODE ###

N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*N
maxi=max(a)
for i in range(N):
  s.append(1+i-a[i])
  if 1+i+a[i]<N:
    num[1+i+a[i]]+=1
for i in range(N):
  if s[i]>=0:
    count+=num[s[i]]
print(count)
from collections import deque

def main(sorted_list):
    if len(sorted_list) == 2:
        print(sorted_list.pop()- sorted_list.popleft())
        return
    if len(sorted_list) == 3:
        print(max(sorted_list[1]+sorted_list[2]-sorted_list[0]*2, -sorted_list[1]-sorted_list[0]+sorted_list[2]*2))
        return
    max_num = sorted_list.pop()
    left = sorted_list.popleft()
    right = sorted_list.popleft()
    ans = 2*max_num - left - right
    status = 'max'

    while sorted_list:
        if status == 'max':
            num = sorted_list.pop()
            status = 'min'
            if left < right:
                ans += num - left
                left = num
            else:
                ans += num - right
                right = num
        else:
            num = sorted_list.popleft()
            status = 'max'
            if left < right:
                ans += right - num
                right = num
            else:
                ans += left - num
                left = num
    print(ans)


if __name__ == '__main__':
    n = int(input())
    sample = []
    for _ in range(n):
        sample.append(int(input()))
    sorted_list = deque(sorted(sample))
    main(sorted_list)


### FIXED CODE ###

def main(string):
    if len(string) == 2:
        return string
    elif len(string) == 3:
        return string[::-1]

if __name__ == '__main__':
    s = input()
    print(main(s))
Num = int(input())
Indata = [0] * num;
Indata = [int(i) for i in input().split()]
MinVal = min(Indata)
MaxVal = max(Indata)
SumVal = sum(Indata)

print(MinVal, MaxVal, SumVal)


### FIXED CODE ###

num = int(input())
inData = [0] * num
inData = [int(i) for i in input().split()]
minVal = min(inData)
maxVal = max(inData)
sumVal = sum(inData)

print(minVal, maxVal, sumVal)
X=list(map(int,input().split()))[1]
L=list(map(int,input().split()))
i=0
d=0
while True:
    if d>=X:
        break
    else:
        d+= L[i]
        i+= 1
print(i+1)

### FIXED CODE ###

N = list(map(int,input().split()))
if N[0]< N[1]:
    print(0)
else:
    print(10)
from pip._vendor.pep517.check import ansi
n, q = map(int, input().split())
s = input()
ans = []
for i in range(0, q):
    l, r = map(int, input().split())
    ans.append(s[l-1: r].replace('AC', ' ').count(' '))
for i in ans:
    print(i)

### FIXED CODE ###

n, q = map(int, input().split())
s = ' ' + input()
heap = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1;
    heap[i] = cnt
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(heap[r] - heap[l])
for i in ans:
    print(i)
n = int(input())
c = list(input())
cFixed = [x for x in c]
cFixed.sort()
for i in range(n):
	if cFixed[i] == "R":
		lastR = i
ans = 0
for i in range(lastR+1):
	if c[i] == "W":
		ans += 1

print(ans)


### FIXED CODE ###

n = int(input())

if n >= 30:
	print("Yes")
else:
	print("No")
kari

### FIXED CODE ###

A,B=map(int,input().split())
print(A*B)
N = int(input())
m = dict()

prev = input()
m[prev] = True
flg = True

for _ in range(N - 1):
  s = input()
  flg = all(flg, s not in m, prev[len(prev) - 1] == s[0])
  m[s] = True
  prev = s

print("Yes" if flg else "No")

### FIXED CODE ###

N = int(input())
m = dict()

prev = input()
m[prev] = True
flg = True

for _ in range(N - 1):
  s = input()
  flg = flg and s not in m
  flg = flg and prev[len(prev) - 1] == s[0]
  m[s] = True
  prev = s

print("Yes" if flg else "No")
N, K = map(int, input().split())
list = []
if K == 1:
  print(0)
else:
  for i in range(N):
    N = abs(N-K)
    list.append(N)
    list = sorted(list)
  print(list[0])

### FIXED CODE ###

N,K = map(int, input().split())
print(min(N%K, K-N%K))
a,b = map(int, input().split())

c = a*b

if c % 2 == 1:
    print(Odd)

else:
    print(Even)

### FIXED CODE ###

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

if (a*b) % 2 == 1:
    print("Odd")

else:
    print("Even")
import math
A, B = input().split()
print(math.floor(A*B))

### FIXED CODE ###

def resolve():
    A, B = input().split()
    ans = int(A)*int(B[0])*100+int(A)*int(B[2:])
    print(str(ans)[:-2] if len(str(ans)) >= 3 else "0")
resolve()
n = int(input())
p = 10
su = 0
while p <= n:
   su += math.floor(n//p)
   p*=5

if n%2==1:
    print(0)
else:
    print(su)

### FIXED CODE ###

n = int(input())
p = 10
su = 0
while p <= n:
   su += n//p
   p*=5

if n%2==1:
    print(0)
else:
    print(su)
import sys
sys.setrecursionlimit(100000)
readline = sys.stdin.readline

N , Q = map(int,readline().rstrip().split())
G = [[] for _ in range(N)]
for n in range(N-1):
    a , b = map(int,readline().rstrip().split())
    G[a-1].append(b-1)
query = []
[query.append( list(map(int,readline().rstrip().split()))) for _ in range(Q) ]
counter = [0] * N 
# visit = []

def dfs(root , x , visit):
    if visit[root] == 0:
        visit[root] = 1
        counter[root] += x
    else:
        return 0
    
    for g in G[root]:
        dfs( g, x , visit)
    
    return 0

def solve():
    for q in query:
        visit = [0] * N
        dfs(q[0]-1,q[1] , visit)
    [print(c) for c in counter]

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

N , Q = map(int,readline().rstrip().split())
G = [[] for _ in range(N)]
for n in range(N-1):
    a , b = map(int,readline().rstrip().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
query = [0] * N
for q in range(Q):
    p , x = map(int,readline().rstrip().split())
    query[p-1] += x
counter = [0] * N 
visit = [0] * N

def dfs(root , x ):
    if visit[root] == 0:
        visit[root] = 1
        x += query[root]
        counter[root] += x
    else:
        return 0
    
    for g in G[root]:
        dfs( g, x )

    return 0

def solve():
    dfs(0 , 0)
    [print(c , end = " " ) for c in counter]
    print("")

if __name__ == "__main__":
    solve()
N = int(input())
A = list(map(int, input().split(" ")))

dp_dict = {}


def dp(i, j):
    if j == 1:
        return A[i]
    # if (i-1)//2 > (N//2)-j:
        # return -1*10e+9
    if (N-1)-i < j:
        return -1*10e+9

    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, N//2))

### FIXED CODE ###

N = int(input())
A = [0]+list(map(int, input().split(" ")))

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

print(dp_list[-1][N//2])
N = int(input())
S = input()

import sys
sys.setrecursionlimit(2000)

pins = set()
def dfs(s, pin, cnt):
    if cnt == 3:
        pins.add(pin)
    for i in range(len(s)):
        dfs(s[i+1:], pin+s[i], cnt+1)
        
dfs(S, '', 0)
print(len(pins))


### FIXED CODE ###

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


pins = set()
pins_check = set()

def bfs():    
    from collections import deque
    queue = deque([(S, '', 0)])
    while queue:
        tmp_s, tmp_pin, tmp_cnt = queue.popleft()
        if tmp_cnt == 3:
            pins.add(tmp_pin)
            continue
        
        for i in range(len(tmp_s)):
            if tmp_pin+tmp_s[i] in pins_check:
                continue
            pins_check.add(tmp_pin+tmp_s[i])
            queue.append((tmp_s[i+1:], tmp_pin+tmp_s[i], tmp_cnt+1))

ans = bfs()
#print(pins)
print(len(pins))
n = int(intput())

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

sa = sorted(a)

if n % 2 == 0:
  k = 0
else:
  k = 1

flag = True

for i,s in enumerate(sa):
  if (i/2)*2+k != s:
    flag = False

if flag:
  print(2**n/2)
else:
  print(0)


### FIXED CODE ###

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

if n % 2 == 0:
  k = 1
  l = 0
else:
  k = 0
  l = 1 

a=1000000007
flag = True 
for i,s in enumerate(sa):
  if ((i+l)//2)*2+k != s:
    flag = False
if flag:
  print(2**(n//2) % a)
else:
  print(0)
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append(list(input().rstrip()))
B = []
for _ in range(M):
    B.append(list(input().rstrip()))
m = len(B[0])
def search(point):
    x, y = point
    for i in range(M):
        if y > N:
            return 0
        a = A[y][x:x + m]
        if a != B[i]:
            return 0
        y += 1
    return 1
for i in range(N):
    for j in range(len(A[0])):
        if search([i, j]):
            print("Yes")
            sys.exit()
print("No")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append(list(input().rstrip()))
B = []
for _ in range(M):
    B.append(list(input().rstrip()))
n = len(A[0])
m = len(B[0])
def search(point):
    x, y = point
    for i in range(M):
        if y > N - 1:
            return 0
        a = A[y][x:x + m]
        if a != B[i]:
            return 0
        y += 1
    return 1
for i in range(N):
    for j in range(n):
        if search([i, j]):
            print("Yes")
            sys.exit()
print("No")