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

import math, sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(1000)
    flag = True
    for i in p:
        temp = 0
        for j in range(n):
            if a[j] % i == 0:
                temp += 1
            if temp == 2:
                flag = False
                break
            while a[j] % i == 0:
                a[j] //= i
        if flag == False:
            break
    if flag == False:
        print("setwise coprime")
    else:
        num = set()
        for i in a:
            if i == 1:
                continue
            if i in num:
                print("setwise coprime")
                break
            else:
                num.add(i)
        else:
            print("pairwise coprime")

### FIXED CODE ###

import math, sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

def prime(n):
    p = []
    min_p = [0 for i in range(n - 1)]
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                if flag[num] == True:
                    min_p[num] = i + 2
                flag[num] = False
                num += i + 2
    return p, min_p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(max(a))
    p_list = {i:0 for i in p[0]}
    min_p = p[1]
    flag = True
    for i in a:
        temp = set()
        while i != 1:
            temp.add(min_p[i - 2])
            i //= min_p[i - 2]
        for j in temp:
            if p_list[j] == 1:
                flag = False
                break
            else:
                p_list[j] += 1
        if flag == False:
            print("setwise coprime")
            break
    else:
        print("pairwise coprime")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    candidateA = []
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    candidateA = A[:tmp_A]
    max_count = current_count = len(candidateA)

    candidateB = []
    weightB = 0
    terminated = False
    for b in B:
        if terminated == True and weightA + weightB > K:
            break

        if len(candidateA)==0 and weightA + weightB + b > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            candidateB.append(b)
            current_count += 1

        elif terminated==False:
            while weightA + weightB + b > K:
                if len(candidateA)>0:
                    weightA -= candidateA.pop()
                    current_count -= 1
                else:
                    terminated=True

            if weightA + weightB + b <= K:
                weightB += b
                candidateB.append(b)
                current_count += 1
        max_count = max(max_count, current_count)

    print(max_count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, K, A, B)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import numpy as np

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[[pivot,rank]] = A[[rank,pivot]]
        for row in range(len(A)):
            if (row != rank and A[row][col]):
                A[row] ^= A[rank]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

use_digit = []
ans = 0
for j in range(60)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = np.zeros((N,len(use_digit)), dtype=bool)
for i in range(N):
    k = 0
    for j in use_digit:
        if A[i]>>j & 1:
            a[i][k] = 1
        else:
            a[i][k] = 0
        k += 1

g = F2_GaussJordan(a,False)

s = np.zeros(len(use_digit),dtype=bool)
row = 0
for j in range(len(use_digit)):
    for i in range(row,N):
        if g[i][j]==1:
            s ^= g[i]
            row = i+1
            break

for j,k in enumerate(s):
    ans += k*2**(use_digit[j]+1)

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

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

ans = 0
for i in range(1 << n):
    biscuits = 0
    for j in range(n):
        if i >> j & 1:
            biscuits = (biscuits + a[j] % 2) % 2
    if biscuits % 2 == p:
        ans += 1
print(ans)

### FIXED CODE ###

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

is_odd = False
for ai in a:
    if ai % 2 == 1:
        is_odd = True
        break

if is_odd:
    ans = 2 ** (n - 1)
else:
    if p == 0:
        ans = 2 ** n
    else:
        ans = 0
print(ans)
### BUGGY CODE ###

n = int(input())
a=list(map(int, input().split()))
b = len(a)
c = 0

for i in range(n-1):
    for j in range(i,n):
        c = c + (a[i] ^ a[j])
        if c>=(10**9+7):
            c = c % (10**9+7)
        
print(c)

### FIXED CODE ###

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

from collections import Counter
s = []

for i in range(n):
    b = bin(a[i])[2:]
    c = len(b)
    s.append("0"*(60-c) + b)
    
ans = 0
for i in range(60):
    zero = 0
    one = 0
    for j in range(n):
        if s[j][i] == "0":
            zero += 1
        else:
            one += 1
            
    temp = zero * one * (2 ** (59-i)) % MOD
    
    ans = (ans + temp) % MOD
    
print(ans)
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))
### BUGGY CODE ###

K,S=map(int,input().split())
count=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                count+=1
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for i in range(K+1):
    for j in range(K+1):
        if 0<=S-i-j<=K:
            count+=1
print(count)
### BUGGY CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += (num0 * num1) * (2 ** d)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

S = list(input())
Q = int(input())

for i in range(Q):
    Q = [i for i in input().split()]
    if Q[0] == "1":
        S = S[::-1]
    else:
        if Q[1] == "1":
            S.insert(0,Q[2])
        elif Q[1] == "2":
            S.append(Q[2])

print("".join(S))


### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

sign = 1
head = ""
tail = ""
for i in range(Q):
    Q = input().split()
    if Q[0] == "1":
        sign *= -1
    else:
        if int(Q[1]) * sign == 1:
            S.appendleft(Q[2])
        elif int(Q[1]) * sign == -1:
            S.append(Q[2])
        elif int(Q[1]) * sign == 2:
            S.append(Q[2])
        elif int(Q[1]) * sign == -2:
            S.appendleft(Q[2])

if sign==1:
    print("".join(S))
elif sign==-1:
    S.reverse()
    print("".join(S))
### BUGGY CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    count = 0
    for i in range(N):
        M = min(P[:i+1])
        if M >= P[i]:
            count += 1
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    count = 1
    num = P[0]
    for i in range(1, N):
        if num >= P[i]:
            count += 1
            num = P[i]
    print(count)


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

import collections
n = int(input())
cnt_lis = []
for i in range(n):
    s = input()
    cnt_lis.append(s)

lis = collections.Counter(cnt_lis)
ans = []
tmp = 0
for i in range(len(lis)):
    if tmp <= lis.most_common()[i][1]:
        ans.append(lis.most_common()[i][0])
        tmp = lis.most_common()[i][1]
    else:
        continue
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
    s = input()
    if s in dic.keys():
        dic[s] += 1
    else:
        dic[s] = 1

max_val = max(dic.values())
k = [key for key in dic if dic[key] == max_val]
for i in sorted(k):
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [(int(_x) % (2 * k), int(_y) % (2 * k) if _c == "W" else (int(_y) + k) % (2 * k))
      for (_x, _y, _c) in xyc]

ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x, _y] += 2
        ans[_x + k, _y] -= 2
        ans[_x, _y + k] -= 2
        ans[_x + k, _y + k] += 2
        ans[_x + k, 0] += 1
        ans[0, _y + k] += 1
        ans[0, 0] += 1
        ans[_x, 0] -= 1
        ans[0, _y] -= 1
    else:
        _x %= k
        _y %= k
        ans[_x, _y] -= 2
        ans[_x + k, _y] += 2
        ans[_x, _y + k] += 2
        ans[_x + k, _y + k] -= 2
        ans[_x + k, 0] -= 1
        ans[0, _y + k] -= 1
        ans[_x, 0] += 1
        ans[0, _y] += 1
print(ans.cumsum(axis=1).cumsum(axis=0).max())

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}


def create_bound(p, K, ub):
    if p - K + 1 >= 0:
        return [(p - K + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - K + 1) % ub, ub)]


for i in range(N):
    x, y, c = input().split()
    nx = int(x) % ub
    ny = (int(y) + ADD[c]) % ub
    for add in [0, K]:
        for xlb, xub in create_bound((nx + add) % ub, K, ub):
            for ylb, yub in create_bound((ny + add) % ub, K, ub):
                b[xlb][ylb] += 1
                b[xlb][yub] -= 1
                b[xub][ylb] -= 1
                b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
    b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
    b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
### BUGGY CODE ###

N, W = map(int, input().split())
w, v = [], []

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

def solve(idx, weight, val):
    if weight > W:
        return -1
    if idx == N:
        return val

    # select
    v1 = solve(idx + 1, weight + w[idx], val + v[idx])

    # not select
    v2 = solve(idx + 1, weight, val)

    return max(v1, v2)

print(solve(0, 0, 0))

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###

s = input()
cnt = 0
a = 0
while True:
    fidx = s.find('10')
    if fidx==-1:
        a = 1
    cnt += s.count('10')
    s = s.replace('10', '')
    fidx = s.find('01')
    if (fidx==-1)and(a==1):
        break
    cnt += s.count('01')
    s = s.replace('01', '')
print(cnt*2)


### FIXED CODE ###

s = input()
print(min(s.count('0'), s.count('1'))*2)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int, input().split()))
if len(a)==1:
  print(int(a[0]/(2**m)))
  exit(0)
a=sorted(a)
for i in range(m):
  x=a.pop(-1)
  bisect.insort_right(a, int(x//2))
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
for _ in range(m):
  tmp_min = heapq.heappop(a)
  heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
  for j in range(n // g + 1):
    if (n - (i * r + j * g)) % b == 0 and (n - (i * r + j * g)) // b >= 0 :
      ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
  for j in range((n - r * i) // g + 1):
    if (n - r * i - g * j) % b == 0 and (n - r * i - g * j) // b >= 0:
      ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
sn = [input().strip('\n') for _ in range(n)]

mod = 10**5 + 7
hs = [[0, ''] for _ in range(mod)]

def hypo(s, Mod):
    h_num = 1
    for i in s:
        h_num = h_num * ord(i) % Mod
    return h_num

for s in sn:
    s = ''.join(sorted(s))
    h = hypo(s, mod)
    if hs[h][0] > 0:
        i = 0
        while True:
            if h + i >= mod :
                h = 0
                i = 0
            if hs[h+i][1] == s:
                hs[h+i][0] += 1
                break
            i += 1
    else:
        hs[h][0] += 1
        hs[h][1] += s

ans = 0
for j, t in hs:
    if j >= 2:
        ans += j * (j-1) / 2

print(int(ans))




### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
sn = [input().strip('\n') for _ in range(n)]

mod = 10**6 + 7
hs = [[0, ''] for _ in range(mod)]

def hypo(s, Mod):
    h_num = 1
    for i in s:
        h_num = h_num * ord(i) % Mod
    return h_num

for s in sn:
    s = ''.join(sorted(s))
    h = hypo(s, mod)
    while True:
        if h >= mod :
            h = 0
        if hs[h][0] == 0:
            hs[h][0] += 1
            hs[h][1] += s
            break
        if hs[h][1] == s:
            hs[h][0] += 1
            break
        h += 1

ans = 0
for j, t in hs:
    if j >= 2:
        ans += j * (j-1) / 2

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

import numpy as np

a = map(int,raw_input().split())
N = a[0]
x = a[1]
A = map(int,raw_input().split())

B = np.zeros(N)
E = np.zeros(N)
D = np.zeros((N,N))
F = np.zeros((N,N))
C = 10000000000*np.ones((N,N))
for idx in xrange(N):
  C[idx] = np.array([A[idx-i]+x*i for i in xrange(N)])
  D[idx] = np.array([A[idx-i] for i in xrange(N)])
  F[idx] = np.array(range(N))
  B[idx] = D[idx][np.where(C[idx]==min(C[idx]))[0][0]]
  E[idx] = F[idx][np.where(C[idx]==min(C[idx]))[0][0]]

print int(sum(B)+max(E)*x)

### FIXED CODE ###

import time
import numpy as np
import copy

tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = list(np.random.randint(m,size=(N)))
  st = time.time()
else:
  N, x = map(int,raw_input().split())
  A = map(int,raw_input().split())

#B = copy.deepcopy(A)
B = A
A = A + A
m = sum(B)
for idx in xrange(1,N):
  for jdx in xrange(N):
    if B[jdx] > A[jdx+N-idx]:
      B[jdx] = A[jdx+N-idx]
#  A = np.append(A, A[0])
#  A = np.delete(A, 0)
#  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)
### BUGGY CODE ###

n,a,b = map(int,input().split())
for i in range(10**100):
    if i*(a+b)==n:
        print(a*i)
        exit()
    elif i*(a+b)>n:
        t = n-(i-1)*(a+b)
        if t>a:
            t = a
        print((i-1)*a+t)
        exit()

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = n // (a+b) * a
rem = n % (a+b)
ans += min(rem,a)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    for i in range(len(A)):
        a = A[:]
        a.pop(i)
        print(max(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    max_val = max(A)
    AA = A[:]
    AA.remove(max_val)
    second_max_val = max(AA)
    for a in A:
        if a != max_val:
            print(max_val)
        else:
            print(second_max_val)

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

n,w_limit = map(int,input().split())
w_ls = [0] * n
v_ls = [0] * n
for i in range(n):
    w_ls[i],v_ls[i] = map(int,input().split())
dp = [[0] * (w_limit+1) for _ in range(n+1)]
for i in range(1,n+1):
    for w in range(w_limit+1):
        if w - w_ls[i-1] >= 0:
            dp[i][w] = dp[i-1][w-w_ls[i-1]] + v_ls[i-1]
        dp[i][w] = max(dp[i][w], dp[i-1][w])
print(dp[-1][w_limit])


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
readline = sys.stdin.buffer.readline

N = int(readline())
A = np.array(list(map(int, readline().split())))
Q = int(readline())

answer = [0] * Q

for i in range(Q):
    B, C = map(int, readline().split())

    A = np.where(A == B, C, A)
    print(np.sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
readline = sys.stdin.buffer.readline

N = int(readline())
A = list(map(int, readline().split()))
Q = int(readline())
d = Counter(A)

total = sum(A)

for _ in range(Q):
    B, C = map(int, readline().split())

    total -= B * d[B]
    total += C * d[B]

    d[C] += d[B]
    d[B] = 0

    print(total)
### BUGGY CODE ###

n=int(input())
hoge=list(map(int,input().split()))
###
def huga(a,b):
  x=max(a,b)
  y=min(a,b)
  z=1
  for i in range(y):
    wa=y-i
    if(x%wa==0 and y%wa==0):
      z=wa
      break
  return z
###
hoge.sort()
ans=hoge[0]
for i in range(n-1):
  ans=huga(ans,hoge[i+1])
  
print(ans)

### FIXED CODE ###

def gcd(a,b):
  if(a<b):
    a,b=b,a
  if(b==0):
    return a
  c= a%b
  return gcd(b,c)

n=int(input())
hoge=list(map(int,input().split()))
hoge.sort()
for i in range(n-1):
  hoge[i+1]=gcd(hoge[i],hoge[i+1])
  
print(hoge[-1])
### BUGGY CODE ###

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

def check(a,list):
    if a==min(list):
        return 1
    else:
        return 0
count=0
for i in range(n):
    count+=check(p[i],p[:i+1])
print(count)
        


### FIXED CODE ###

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

count=0
min=p[0]
for i in range(n):
    if p[i]<=min:
        count+=1
        min=p[i]
print(count)