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

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()

        dp = [[0, 0] for i in range(N)]
        # 人１がビットを最後に立てた後に０にできるなら０にならない
        L = max(A).bit_length()

        ret = 0

        B = [A[i] for i in range(N) if S[i] == '0']
        C = [A[i] for i in range(N) if S[i] == '1']

        s1 = set([0])
        s0 = set([0])

        for x in B:
            tmp = set()
            for y in s0:
                tmp.add(y ^ x)
            s0 |= tmp

        for x in C:
            tmp = set()
            for y in s1:
                tmp.add(y ^ x)
            s1 |= tmp

        if len(s1 - s0) > 0:
            print(1)
        else:
            print(0)


main()


### FIXED CODE ###

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L
        ID = A.index(max(A))

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            flag = False
            if x.bit_length() == 60:
                flag = True
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        L2 = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                L2 = max(L2, A[i].bit_length())
                update(A[i])
        print(res)



main()
### BUGGY CODE ###

# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
m = int(input())
uv = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

e = [[] for _ in range(n)]
i = 0
for a, b in ab:
    e[a].append([b, i])
    e[b].append([a, i])
    i += 1

def func(x, g, p):
    #print(x, g, p, e[x])
    if len(e[x]) == 1 and p != -1:
        return -1
    for edge in e[x]:
        if edge[0] == p:
            continue
        elif edge[0] == g:
            #print(edge)
            return 1 << edge[1]
        temp = func(edge[0], g, x)
        #print(temp, x, g, p)
        if temp >= 0:
            #print(edge[1])
            return temp + (1 << edge[1])
    return -1

p = []
for u, v in uv:
    p.append(func(u, v, -1))

#print(p)
flag = -1
ans = 2 ** (n-1)
#print(ans)
base = 2 ** (n-1)
for i in range(1, 1 << m):
    temp = list(reversed(list(str(bin(i)))[2:]))
    c = 0
    #print(temp)
    for j, x in enumerate(temp):
        if x == '1':
            c = c | p[j]
    #print(bin(base + c))
    hoge = str(bin(base + c)).count('0') - 1
    if temp.count('1') % 2 == 0:
        flag = 1
    else:
       flag = -1
    ans += flag * (2 ** hoge)
    #flag *= -1
print(ans)


### FIXED CODE ###

# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
m = int(input())
uv = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

e = [[] for _ in range(n)]
i = 0
for a, b in ab:
    e[a].append([b, i])
    e[b].append([a, i])
    i += 1

def func(x, g, p):
    #print(x, g, p, e[x])
    if len(e[x]) == 1 and p != -1:
        return -1
    for edge in e[x]:
        if edge[0] == p:
            continue
        elif edge[0] == g:
            #print(edge)
            return 1 << edge[1]
        temp = func(edge[0], g, x)
        #print(temp, x, g, p)
        if temp >= 0:
            #print(edge[1])
            return temp + (1 << edge[1])
    return -1

p = []
for u, v in uv:
    p.append(func(u, v, -1))

#print(p)
flag = -1
ans = 2 ** (n-1)
#print(ans)
base = 2 ** (n-1)
for i in range(1, 1 << m):
    temp = list(reversed(list(str(bin(i)))[2:]))
    c = 0
    #print(temp)
    for j, x in enumerate(temp):
        if x == '1':
            c = c | p[j]
    #print(bin(base + c))
    hoge = str(bin(base + c)).count('0') - 1
    if temp.count('1') % 2 == 0:
        flag = 1
    else:
       flag = -1
    ans += flag * (2 ** hoge)
    #flag *= -1
print(ans)
### BUGGY CODE ###

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

mod = (10**9)+7
goukei = 0

for i in range(N-1):
  Ai = A[i]
  AJ = A[i+1:]
  goukei += sum(AJ)*Ai
  goukei = goukei%mod

print(goukei)

### FIXED CODE ###

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

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

mod = (10**9)+7
sumA = sum(A)%mod
sumSq = sum([(i*i)%mod for i in A])%mod
r = (((sumA*sumA)%mod)-sumSq) * modinv(2, mod)
print(r%mod)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

cnt = 0

maxr = N // R + 1
maxg = N // G + 1
maxb = N // B + 1

for r in range(0, maxr+1):
  if R*r > N: break
  for g in range(0, maxg+1):
    if R*r + G*g > N: break
    for b in range(0, maxb+1):
      p = R*r + G*g + B*b
      if p == N:
        cnt += 1
        break
      elif p > N: break
        
print(cnt)

### FIXED CODE ###

###template###
import sys
input = sys.stdin.readline
def mi(): return map(int, input().split())
###template###

Rt, Gt, Bt, N = mi()

R = max(Rt, Gt, Bt)
B = min(Rt, Gt, Bt)
G = Rt+Gt+Bt-R-B

cnt = 0
if G == 1 and B == 1:
  for i in range(N//R+1):
    cnt += (N-R*i)+1
  print(cnt)
  exit()

for i in range(N//R+1):
  for j in range((N-R*i)//G+1):
    #残り必要ボール数
    if (N - R*i - G*j)%B == 0:
      cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
l = []
for _ in range(n):
    a = int(input())
    l.append(a)

ans = []
tmp = 0
cnt = 0

for i in range(n):
    tmp = []
    for m in range(n):
        if i != m:
            tmp.append(l[m])
    ans.append(max(tmp))


for j in range(n):
    print(ans[j])

### FIXED CODE ###

n = int(input())
l = []
for _ in range(n):
    a = int(input())
    l.append(a)

l2 = l
l2 = sorted(l2)
l2.reverse()
max = max(l)


ans = []
if l2[1] == max:
    for i in range(n):
        print(max)
else:
    for j in l:
        if j != max:
            print(max)
        else:
            print(l2[1])
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    dp = [[0] * (M+1) for i in range(N+1)]
    
    for i in range(N):
        for s in range(M+1):
            a, b = A[i]
            if s-a >= 0:
                dp[i+1][s] = max(dp[i+1][s], dp[i][s-a] + b)
            dp[i+1][s] = max(dp[i+1][s], dp[i][s])
    return dp[N][M]

print(solve())

### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    dp = [[0] * (M+1) for i in range(N+1)]
    
    for i in range(N):
        for s in range(M+1):
            a, b = A[i]
            if s-a >= 0:
                dp[i+1][s] = max(dp[i+1][s], dp[i][s-a] + b)
            dp[i+1][s] = max(dp[i+1][s], dp[i][s])
    return dp[N][M]

print(solve())
### BUGGY CODE ###

#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

from math import factorial
def kumiawase_num(n, r): # 組み合わせ n「C」r
    if  n<r:
        return 0
    return factorial(n) // (factorial(n - r) * factorial(r))

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
mod =10**9 +7
N,M = map(int, input().split())
a =soinsu_bunkai(M)
ans =1
for i in a.values():
    x =kumiawase_num(N +i -1,i)
    x %=mod
    ans *=x
print(ans %mod)

### FIXED CODE ###

#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

# 組み合わせの総数 p=10**9+7 で割ったあまりを求める Satoooh Blog 2020/02/27 4分 
"""n<10**7 , p は素数"""
def cmb(n, r, p):

    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p



# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
mod =10**9 +7
p =mod
N,M = map(int, input().split())
a =soinsu_bunkai(M)
ans =1

n = 10 ** 6  # n は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

#mod p における n の逆元の計算
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in a.values():
    x =cmb(N +i -1,i,mod)
    ans *=x
print(ans %mod)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse = True)
ans = 0
for i in range(n):
    if a.count(a[i]) >= 4:
        ans = a[i]*a[i]
        break
    elif a.count(a[i]) >=2:
        for j in range(i+a.count(a[i]),n):
            if a.count(a[j]) >=2:
                ans = a[i]*a[j]
                break
        break
print(ans)

### FIXED CODE ###

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

a.sort(reverse = True)
ans = 0
b = a.copy()
b = list(set(b))
b.sort(reverse = True)
c = [0]*len(b)
j = 0
c[j] = 1
for i in range(1,n):
    if a[i-1] == a[i]:
        c[j] +=1
    else:
        j+=1
        c[j] +=1
for i in range(len(b)):
    if c[i] >= 4:    
        
        ans = b[i]*b[i]
        break
    elif c[i] >= 2:
        for j in range(i+1,len(b)):
            if c[j] >= 2:
                ans = b[i]*b[j]
                break
        break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

s = input()
q = int(input())
query = ["" for _ in range(q)]

for i in range(q):
    query = input()
    if query == "1":
        s = "".join(list(reversed(s)))
        #print(s)
    else:
        q2 = query.split()
        if q2[1] == "1":
            s = q2[2]+s
        else:
            s = s + q2[2]
        #print(s)

print(s)



### FIXED CODE ###

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

s = list(input())
q = int(input())

a = deque(s)
reverse = False

for i in range(q):
    query = input()
    if query == "1":
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        x, q2_1, q2_2 = query.split()
        if q2_1 == "1":
            if reverse:
                a.append(q2_2)
            else:
                a.appendleft(q2_2)
        else:
            if reverse:
                a.appendleft(q2_2)
            else:
                a.append(q2_2)

s = list(a)
if reverse:
    s = s[::-1]
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###

import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)


### FIXED CODE ###

import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)
    kari %= mod

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    kari *= pow(ai[i],mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = [INT() for i in range(M)]

    dp = [1] * (N + 1)
    for a in A:
        dp[a] = 0

    for i in range(N-1):
        if not i+2 in A:
            dp[i+2] = (dp[i] + dp[i+1]) % mod
        else:
            dp[i+2] = 0
     
    print(dp[N])



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = [INT() for i in range(M)]

    dp = [1] * (N + 1)
    for a in A:
        dp[a] = 0

    for i in range(N-1):
        dp[i+2] = dp[i+2] * (dp[i] + dp[i+1]) % mod
     
    print(dp[N])


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


from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  if D[current][goal] > 0:
    return D[current][goal]
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      D[current][goal] = cost
      D[goal][current] = cost
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = bfs(i, v)
    takahashi = bfs(i, u)
    if aoki > takahashi:
      distances.append(aoki)

print(max(distances)-1)



### FIXED CODE ###

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)
### BUGGY CODE ###

n = int(input())
s = input()

ans = ''

ans += s[0]
prev = s[0]

for i in range(1, n):
    if s[i] != prev:
        prev = s[i]
        ans += prev

print(len(ans))


### FIXED CODE ###

n = int(input())
s = input()

prev = s[0]
ans = 1

for i in range(1, len(s)):
    if s[i] != prev:
        prev = s[i]
        ans += 1

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

from math import factorial as fact

x,y = map(int,input().split())
mod =10**9+7

a=(-x+2*y)//3
b=(2*x-y)//3
n=a+b

if a+2*b==x and b+2*a==y and a>=0 and b>=0:
    ans=fact(n)%mod * pow(fact(n-a),mod-2,mod)*pow(fact(a),mod-2,mod)
    print(ans%mod)
else:
    print("0")

### FIXED CODE ###

x,y = map(int,input().split())
mod =10**9+7

a=(-x+2*y)//3
b=(2*x-y)//3
n=a+b

def fact(x,p):
    ret=1
    for i in range(1,x+1):
        ret*=i
        ret%=p
    return ret


if a+2*b==x and b+2*a==y and a>=0 and b>=0:
    ans=fact(n,mod) * pow(fact(b,mod),mod-2,mod)*pow(fact(a,mod),mod-2,mod)
    print(ans%mod)
else:
    print("0")
### BUGGY CODE ###

n = int(input())
towns = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10 ** 18
ans = [INF] * (n + 1)

default_dist = [min(abs(x), abs(y)) for x, y, p in towns]

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    i = 0
    t = bit
    selected = []
    is_selected = [False] * n
    while t:
        if t & 1:
            selected.append(towns[i])
            is_selected[i] = True
        t >>= 1
        i += 1

    for bit2 in range(1 << k):
        cost = 0
        for i in range(n):
            if is_selected[i]:
                continue
            town_dist = default_dist[i]
            t = bit2
            x, y, p = towns[i]
            for j in range(k):
                if t & 1:
                    town_dist = min(town_dist, abs(selected[j][1] - y))
                else:
                    town_dist = min(town_dist, abs(selected[j][0] - x))
                t >>= 1
            cost += town_dist * p
        ans[k] = min(ans[k], cost)

print('\n'.join(map(str, ans)))


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    xxx = inp[1::3]
    yyy = inp[2::3]
    ppp = inp[3::3]

    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    default_dist = np.zeros(n, dtype=np.int64)
    for i in range(n):
        default_dist[i] = min(abs(xxx[i]), abs(yyy[i]))

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)

        i = 0
        cur = 0
        t = bit
        selected = np.zeros(k, dtype=np.int64)
        is_selected = np.zeros(n, dtype=np.int8)
        while t:
            if t & 1:
                selected[cur] = i
                is_selected[i] = 1
                cur += 1
            t >>= 1
            i += 1

        for bit2 in range(1 << k):
            cost = 0
            for i in range(n):
                if is_selected[i]:
                    continue
                town_dist = default_dist[i]
                t = bit2
                for j in range(k):
                    if t & 1:
                        town_dist = min(town_dist, abs(yyy[selected[j]] - yyy[i]))
                    else:
                        town_dist = min(town_dist, abs(xxx[selected[j]] - xxx[i]))
                    t >>= 1
                cost += town_dist * ppp[i]
            kk = len(selected)
            ans[kk] = min(ans[kk], cost)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if min(P[:i + 1]) >= P[i]:
        cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
curr_min = 0
for i in range(N):
    if not curr_min:
        curr_min = P[i]
        cnt += 1
    else:
        if P[i] <= curr_min:
            curr_min = P[i]
            cnt += 1

print(cnt)
### BUGGY CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 6000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 50))
    if ans < t:
      ans = t

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

print(ans)