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

n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]


def check(a):
  sum = 0
  for i in range(len(a)):
    if(i == 0):
      sum += a[0]
      continue
    if(sum > 0):
      sum += a[i]
      if(a[i] == 0 or sum >= 0):
        return (i, -1)

    else:
      sum += a[i]
      if(a[i] == 0 or sum <= 0):
        return (i, +1)



  return True

ans = 0
while(True):
  c = check(a)
  if(c == True):
    break

  a[c[0]] += c[1]

  ans += 1



print(ans)

### FIXED CODE ###


def check1(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
    else:
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
  return ans

def check2(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
    else:
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
  return ans



n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]
a2 = list(a)

ans1 = check1(a)
ans2 = check2(a2)


print(ans1) if(ans1<ans2) else print(ans2)
### BUGGY CODE ###

import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if union[i] is union[j]:continue
    tmp = union[j][:]
    while tmp:
        k = heapq.heappop(tmp)
        union[k] = union[i]
        heapq.heappush(union[i],k)
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
B = []
for i in range(n):
    B.append(A.pop(0))
    B.reverse()
print(' '.join(map(str, B)))

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
odd = A[1::2]
even = A[0::2]

if len(A) % 2 == 0:
    odd.reverse()
    ans = odd + even
else:
    even.reverse()
    ans = even + odd
    
print(' '.join(map(str, ans)))
### BUGGY CODE ###

N, K  = map(int, input().split())
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * N
dp[0] = 0
dp[1] = abs(h[1]- h[0])
for i in range(2, N):
    H = h[i]
    dp[i] = min( [dp[j] + abs(h[j] - H) for j in range(max(0, i-K),i)])
print(dp[N-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    sort_A = sorted(A, reverse=True)
    set_A = sorted(set(sort_A), reverse=True)

    max_num = 0

    for a in set_A:
        if sort_A.count(a) >= 2:
            if max_num == 0:
                max_num = a
                if sort_A.count(a) >= 4:
                    print(a * a)
                    exit()
            else:
                print(max_num * a)
                exit()

    print(0)

main()

### FIXED CODE ###

import collections

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    B = collections.Counter(A)

    c = []

    for k, v in B.items():
        if v >= 2:
            c.append(k)
        if v >= 4:
            c.append(k)
    if len(c) < 2:
        print(0)
    else:
        c.sort()
        print(c[-1] * c[-2])

main()
### BUGGY CODE ###

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

N = int(input().strip())
P_list = list(map(int, input().rstrip().split()))
#-----

cnt = 0
for i in range(len(P_list)):
    for j in range(i+1):
        if P_list[j] < P_list[i]:
            break
    else:
        cnt += 1

print(cnt)


### FIXED CODE ###

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

N = int(input().strip())
P_list = list(map(int, input().rstrip().split()))
#-----
min_P = float("inf")
cnt = 0

for p in P_list:
    if min_P >= p:
        cnt += 1
        min_P = min(min_P, p)

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

import heapq

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()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

V = [[[0] * x for i in range(y)] for j in range(z)]

Q = []
i = 0
j = 0
l = 0
heapq.heappush(Q, (-(A[0]+B[0]+C[0]), i, j, l))
V[i][j][l] = 1
ans = heapq.heappop(Q)
print(-ans[0])
i = ans[1]
j = ans[2]
l = ans[3]

for ii in range(k-1):
    if i+1 < x and V[i+1][j][l] == 0:
        V[i+1][j][l] = 1
        heapq.heappush(Q, (-(A[i+1]+B[j]+C[l]), i+1, j, l))
    if j+1 < y and V[i][j+1][l] == 0:
        V[i][j+1][l] = 1
        heapq.heappush(Q, (-(A[i]+B[j+1]+C[l]), i, j+1, l))
    if l+1 < z and V[i][j][l+1] == 0:
        V[i][j][l+1] = 1
        heapq.heappush(Q, (-(A[i]+B[j]+C[l+1]), i, j, l+1))
    ans = heapq.heappop(Q)
    print(-ans[0])
    i = ans[1]
    j = ans[2]
    l = ans[3]


### 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()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = [0] * (min(k, x) * min(k, y))

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = [0] * (min(k, len(D)) * min(k, z))

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1, k + 1):
        for c in range(1,k+1):
            s += gcd(a, b, c)

print(s)

### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())
s = 0

# a = b = c -> gcd(a,a,a) -> a
for a in range(1, k+1):
    s += a

# a = b, a < c -> gcd(a, c)と同じ -> gcd(c, a)も同じ 6倍
for a in range(1, k+1):
    for b in range(a+1, k+1):
        s += gcd(a, a, b) * 6

# a < b < c -> gcd(a, b, c)と同じ -> 6通り

for a in range(1, k+1):
    for b in range(a+1, k+1):
        for c in range(b+1, k+1):
            s += gcd(a, b, c) * 6

print(s)
### BUGGY CODE ###

n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n+1):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
def f(i,w):
    if dp[i][w]>=0:
        return dp[i][w]
    else:
        if i==n:
            return 0
        else:
            if w_list[i]<=w:
                a=max(f(i+1,w),f(i+1,w-w_list[i])+v_list[i])
                dp[i][w]=a
                return a
            else:
                a=f(i+1,w)
                dp[i][w]=a
                return a
print(f(0,W))




### FIXED CODE ###

n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
dp_sub=[]
for j in range(W+1):
    dp_sub.append(0)
dp.append(dp_sub)
for i in range(n):
    i_=n-1-i
    for j in range(W+1):
        if w_list[i_]<=j:
            dp[i_][j]=max(dp[i_+1][j],dp[i_+1][j-w_list[i_]]+v_list[i_])
        else:
            dp[i_][j]=dp[i_+1][j]
print(dp[0][W])
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l = [0] * q
r = [0] * q
ans = ""
table = [1 if s[i:i+2] == "AC" else 0 for i in range(n)]   
for i in range(q):
  l[i], r[i] = [int(j) for j in input().split()]
  ans = ans+str(sum(table[l[i]-1:r[i]-1]))+"\n"
print(ans)

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
ans = ""
table = [0] * n
cnt = 0
for i in range(n-1):
  if s[i:i+2] == "AC":
    cnt += 1
  table[i+1] = cnt
for i in range(q):
  l, r = [int(j) for j in input().split()]
  print(table[r-1] - table[l-1])
### BUGGY CODE ###

# N 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * N
F = [True] * N

for n in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if a in T.keys():
        T[a].append([b, c])
    else:
        T[a] = []
        T[a].append([b, c])
    if b in T.keys():
        T[b].append([b, c])
    else:
        T[b] = []
        T[b].append([a, c])

Q, K = map(int, input().split())

K -= 1

D[K] = 0
F[K] = False

L = [K]

while sum(F) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

for q in range(Q):
    x, y = map(int, input().split())
    x   -= 1
    y   -= 1
    print(D[x] + D[y])


### FIXED CODE ###

# N 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * (N+1)
F = [True] * (N+1)

for n in range(N+1):
    T[n] = []

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

Q, K = map(int, input().split())

D[K] = 0
F[K] = False

L = [K]

while len(L) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

for q in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

x, y, z, t = map(int, readline().split())
a = sorted(map(int, readline().split()), reverse=True)
b = sorted(map(int, readline().split()), reverse=True)
c = sorted(map(int, readline().split()), reverse=True)

ans = []

for i in range(len(a)):
    for j in range(len(b)):
        ans.append(a[i] + b[j])

ans = sorted(ans, reverse=True)
fin_ans = []
for j in range(len(c)):
    for i in range(min(len(ans), t)):
        fin_ans.append(ans[i] + c[j])

fin_ans = sorted(fin_ans, reverse=True)

for i in fin_ans[:t]:
    print(i)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

x, y, z, t = map(int, readline().split())
a = sorted(map(int, readline().split()), reverse=True)
b = sorted(map(int, readline().split()), reverse=True)
c = sorted(map(int, readline().split()), reverse=True)

ans = []

for i in range(len(a)):
    for j in range(len(b)):
        ans.append(a[i] + b[j])

ans = sorted(ans, reverse=True)
fin_ans = []
for j in range(len(c)):
    for i in range(min(len(ans), t)):
        fin_ans.append(ans[i] + c[j])

fin_ans = sorted(fin_ans, reverse=True)

for i in fin_ans[:t]:
    print(i)
### BUGGY CODE ###

import sys

n, x=map(int, input().split())
A=list(map(int, input().split()))

ans=0
for i in range(n-1):
    while(A[i]+A[i+1]>x and A[i+1]>0):
        A[i+1]=A[i+1]-1
        ans=ans+1
    while(A[i]+A[i+1]>x and A[i]>0):
        A[i]=A[i]-1
        ans=ans+1
    if A[i]+A[i+1]>x:
        print(0)
        sys.exit()
print(ans)


### FIXED CODE ###

import sys

n, x=map(int, input().split())
A=list(map(int, input().split()))

ans=0
for i in range(n-1):
    next_sum=A[i]+A[i+1]
    if next_sum>x:
        if next_sum-x<=A[i+1]:
            A[i+1]=A[i+1]-(next_sum-x)
            ans=ans+(next_sum-x)
        else:
            ans=ans+A[i+1]
            if next_sum-x-A[i+1]<=A[i]:
                A[i]=A[i]-(next_sum-x-A[i+1])
                ans=ans+(next_sum-x-A[i+1])
            else:
                print(0)
                sys.exit()
            A[i+1]=0
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  bit =0
  i = "{0:03d}".format(i)
  a,b,c = i[0],i[1],i[2]
  for j in range(n):
    if bit==1:
              break
    if s[j]==a and bit==0:
      for k in range(j+1,n):
        if bit==1:
              break
        if s[k]==b :
          for m in range(k+1,n):
            if bit==1:
              break
            if s[m]==c :
              cou += 1
              bit = 1 
print(cou)



### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
s = input()

q = []
tmp = 0

if len(s) == 1:
    if k >= 1 or s[0] == '1':
        print(1)
    else:
        print(0)
else:
    if s[0] == '0':
        q.append(0)
    for i in range(len(s)):
        if i == 0:
            tmp += 1
        elif i != len(s)-1:
            if s[i] == s[i-1]:
                tmp += 1
            else:
                q.append(tmp)
                tmp = 1
        else:
            if s[i] == s[i-1]:
                tmp += 1
                q.append(tmp)
            else:
                q.append(tmp)
                q.append(1)
    if s[len(s)-1] == '0':
        q.append(0)

    tmp = 0
    max_k = min(math.ceil(len(q)/2), k)
    ans = []
    if max_k == math.ceil(len(q)/2):
        max_k -= 1
    for i in range(0, len(q) - 2 * max_k, 2):
        ans.append(sum(q[i:i+2*max_k+1]))

    print(max(ans))

### FIXED CODE ###

import math
n, k = map(int, input().split())
s = input()

q = []
tmp = 0

if len(s) == 1:
    if k >= 1 or s[0] == '1':
        print(1)
    else:
        print(0)
else:
    if s[0] == '0':
        q.append(0)
    for i in range(len(s)):
        if i == 0:
            tmp += 1
        elif i != len(s)-1:
            if s[i] == s[i-1]:
                tmp += 1
            else:
                q.append(tmp)
                tmp = 1
        else:
            if s[i] == s[i-1]:
                tmp += 1
                q.append(tmp)
            else:
                q.append(tmp)
                q.append(1)
    if s[len(s)-1] == '0':
        q.append(0)

    tmp = 0
    max_k = min(math.ceil(len(q)/2), k)
    """
    if len(q) == 1:
        if s[0] == '0' and k == 0:
            ans.append(0)
        else:
            ans.append(q[0])

    #先頭、末尾が0の時
    elif s[0] == '0' and len(q) % 2 == 1:
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[:+2*max_k]))
        ans.append(sum(q[-2*max_k+1:]))
    #先頭0末尾1
    elif s[0] == '0' :
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[:2*max_k]))
    #先頭1末尾0
    elif len(q) % 2 == 0:
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[-2*max_k+1:]))
    else:
        if max_k == math.ceil(len(q)/2):
            max_k -= 1
        for i in range(0, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))

    """
    #先頭1末尾1
    left = 0
    right = 0
    tmp = 0
    ans = 0
    for i in range(0, len(q), 2):
        next_left = i
        next_right = min(i + 2 * k+1, len(q))

        while (next_left > left):
            tmp -= q[left]
            left += 1

        while (next_right > right):
            tmp += q[right]
            right += 1

        ans = max(ans, tmp)
    print(ans)
### BUGGY CODE ###

import math

def combination_count(n,r):
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N=int(input())
a=list(map(int,input().split()))
maxoutput=0
output=0
n=0
r=0

a.sort(reverse=True)

for i in range(N):
  for j in range(i+1,N):
    output=combination_count(a[i],a[j])
    if output>maxoutput:
      maxoutput=output
      n=a[i]
      r=a[j]
    else:
      break;
print(n,r)

### FIXED CODE ###

import math

def combination_count(n,r):
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N=int(input())
a=list(map(int,input().split()))
maxoutput=0
output=0


a.sort(reverse=True)
n=a[0]
r=a[N-1]

for i in range(1,N):
  if abs(r-n/2)>abs(a[i]-n/2):
    r=a[i]
print(n,r)
### BUGGY CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
M=np.array(M)
c_list=[]
ans=0
for i in range(1,max(M)+1):
    num=np.count_nonzero(M == i)
    ans+=(num*(num-1))//2
for k in range(N):
    num=(np.count_nonzero(M ==M[k]))-1
    print(ans-num)

### FIXED CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
num_list=np.array([0]*(2*10**5+1))
ans=0
for i in M:
    num_list[i-1]+=1
ans=sum(num_list*(num_list-1))//2
for k in range(N):
    num=num_list[M[k]-1]-1
    print(ans-num)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==True: 
    if a not in A:
      ans+=1
    i=1
    k=a
    while k<=max_a:
      dp[k]=False
      i+=1
      k=a*i
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
max_a=A[-1]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  #print(a)
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    dd =defaultdict(int)
    for a in A:
        dd[a%(2*t)] +=1
    L=[i%(2*t) for i in B]
    L.sort()
    #print(K,L)
    a = 0
    for k,l in dd.items():
        x = bisect_left(L,2*t-k)-bisect_left(L,t-k)
        y = bisect_left(L,4*t-k)-bisect_left(L,3*t-k)
        #print(x,y)
        a =(a+x*l+y*l)%2
    num[i]=a
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)



### FIXED CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)
### BUGGY CODE ###

s=list(input())
s=[int(i) for i in s]
mods=[0]
for i in range(len(s)):
    now=(s[-1-i]*(10**i))%2019
    mods.append((mods[-1]+now)%2019)
mods=mods[::-1]
from collections import Counter
c=dict(Counter(mods))
ans=0
for k in c.keys():
    ans+=c[k]*(c[k]-1)//2
print(ans)

### FIXED CODE ###

s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce
import itertools
import math

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

K = int(input())

if K == 1:
    ans = 1
elif K == 2:
    ans = 9
else:
    ans = 0
    for i in range(1, K+1):
        ans += i
        for j in range(i+1, K+1):
            ans += gcd(i, j) * 6
            for k in range(j+1, K+1):
                ans += gcd(i, j, k) * 6

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce
import itertools
import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

if K == 1:
    ans = 1
elif K == 2:
    ans = 9
else:
    ans = 0
    for i in range(1, K+1):
        ans += i
        for j in range(i+1, K+1):
            ans += gcd(i, j) * 6
            for k in range(j+1, K+1):
                ans += gcd(i, j, k) * 6

print(ans)