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

# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for val in A:
    if count[val] >= 2:
        ans += 1
        happend.add(val)
        continue
    for j in range(1, int(val**(1/2))+1):
        if val % j == 0 and (j in happend or val//j in happend):
            ans += 1
            break
    happend.add(val)

print(N-ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  # 0~max(A)の数についてのリスト
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            # aが存在したという証拠だけは残しておく
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)
### BUGGY CODE ###

import sys

N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [i for i in P if 1 <= i and i <= 10**3]
Q = []
R = []
r = 0

if not 1 <= K <= N <= 2*10**5:
    sys.exit()

for i in range(N):
    q = (1 + P[i]) / 2
    Q.append(q)
    
for j in range(N-K+1):
    r = sum(Q[j:j+K])
    R.append(r)
print(max(R))

### FIXED CODE ###

import sys

N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [i for i in P if 1 <= i and i <= 10**3]
Q = [] # 期待値リスト
S = [] # 累積和
T = [] # 隣接するK個の期待値
s=0

if not 1 <= K <= N <= 2*10**5:
    sys.exit()

for i in range(N):
    # q = sum(range(1, P[i]+1)) / P[i]
    q = (1 + P[i]) / 2
    Q.append(q)
    s += q
    S.append(s)
    if i == K-1:
        T.append(S[i])
    if i > K-1:
        T.append(S[i]-S[i-K])
print(max(T))
### BUGGY CODE ###

n=int(input())
k=list(input())

kk=0
for i in range(1000):
  if i<10:
    p=['0','0',str(i)]
  elif i<100:
    p=['0',str(i)[0],str(i)[1]]
  else:
    p=list(str(i))
    
    
  flag=False
  for x in range(n-2):
    if flag==True:break
    if k[x]!=p[0]:continue
    else:
      for y in range(x+1,n-1):
        if flag==True:break
        if k[y]!=p[1]:continue
        else:
          for z in range(y+1,n):
            if k[z]!=p[2]:continue
            else:
              flag=True
              break
  
  if flag==True:
    #print(i)
    kk+=1
  else:pass
print(kk)

### FIXED CODE ###

n=int(input())
k=list(input())

kk=0
for i in range(1000):
  if i<10:
    p=['0','0',str(i)]
  elif i<100:
    p=['0',str(i)[0],str(i)[1]]
  else:
    p=list(str(i))
    
  flag=0
  for w in k:
    if w==p[flag]:
      flag+=1
    if flag==3:
      break
  
  if flag==3:
    #print(i)
    kk+=1
  else:pass

print(kk)
### BUGGY CODE ###

from math import sqrt
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i, val in enumerate(A):
    curr_set = set(A[:i] + A[i+1:])
    if val in curr_set:
        continue
    for j in range(1, int(sqrt(val)) + 1):
        if (val % j == 0 and j in curr_set) or val / j in curr_set:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

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

A.sort()
max_A = A[-1]
arr = [0] * (max_A + 1)

for val in A:
    arr[val] += 1
    if arr[val] == 1:
        for j in range(2*val, max_A + 1, val):
            arr[j] += 2

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

N = int(input())
A = list(map(int, input().split()))
lis = [0] * N
for i in range(1, N+1):
  x = A.index(i)
  lis[i-1] = x+1
lis = map(str, lis)
ans = " ".join(lis)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
lis = [0] * N
k = 1
for i in A:
  lis[i-1] = k
  k += 1
lis = map(str, lis)
ans = " ".join(lis)
print(ans)
### BUGGY CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n,k=map(int,readline().split())

if k==1:
	print("0")

else:
	while n>k//2:
		n=abs(n-k)
	
	print(n)



### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n,k=map(int,readline().split())

if k==1:
	print("0")

else:
	n=n%k
	while n>k//2:
		n=abs(n-k)
	
	print(n)
### BUGGY CODE ###

#ABC070-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

def fctr1(n): #[[素因数,数]]を出力
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

n=I()
t=[]
elm=dict()
for i in range(n):
    tmp=I()
    t.append(tmp)
for i in range(n):
    f=fctr1(t[i])
    for j in f:
        if j[0] in elm:
            elm[j[0]]=max(elm[j[0]],j[1])
        else:
            elm[j[0]]=j[1]
ans=1
for i in elm:
    ans*=pow(i,elm[i])
print(ans)

### FIXED CODE ###

#ABC070-C TLE
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

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

def lcm(a,b):
    g=gcd(a,b)
    return a*b//g

n=I()
t=[]
ans=1
for i in range(n):
    tmp=I()
    ans=lcm(ans,tmp)
print(ans)
### BUGGY CODE ###

# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    nums.sort()

    check = [False] * (10 ** 6 + 1)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = True

    ans = 0
    for i in range(n):
        if check[nums[i]] == False:
            ans += 1
        cnt = nums[i] * 2
        while cnt < 10 ** 6 + 1:
            check[cnt] = True
            cnt += nums[i]
    print(ans)

    
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    nums.sort()

    check = [False] * (10 ** 6 + 1)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = True
    #print(nums)
    ans = 0
    for i in range(n):
        if check[nums[i]] == False:
            ans += 1
        if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
            cnt = nums[i] * 2
            while cnt < 10 ** 6 + 1:
                #print(cnt)
                check[cnt] = True
                cnt += nums[i]
        #print(ans)
    print(ans)

    
    return

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

# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            # if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
            #     break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
sys.stderr.write(str(n)+' '+str(k)+' '+str(q)+'\n')

#canTravel = True
#t_pre, x_pre, y_pre = 0,0,0

arr = np.full(n, k, dtype=np.int64)

for i in range(q):
  a_i = int(input())
  
  for j in range(n):
    if j+1 != a_i:
      arr[j] -= 1

  sys.stderr.write(str(i+1)+': ')
  for j in range(n):
    sys.stderr.write(str(arr[j])+' ')
  sys.stderr.write('\n')

for j in range(n):
  if arr[j] > 0:
    print("Yes")
  else:
    print("No")

#if canTravel:
#  print("Yes")
#else:
#  print("No")

sys.stderr.write('\n')


### FIXED CODE ###

import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
arr = np.full(n, k-q, dtype=np.int64)

for i in range(q):
  a_i = int(input()) 
  arr[a_i-1] += 1

for j in range(n):
  if arr[j] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

A,B,Q=list(map(int,input().split()))
s=[0]*(A+2)
t=[0]*(B+2)
X=[0]*Q
s[0] = -float('inf')
s[A+1] = float('inf')
t[0] = -float('inf')
t[B+1] = float('inf')
for i in range(1,A+1):
    s[i] = int(input())
for i in range(1,B+1):
    t[i] = int(input())
for i in range(Q):
    X[i] = int(input())

import bisect
import numpy as np

def dec(x,s,t):
    s_ = s-x
    t_ = t-x
    as_ = abs(s_)
    at_ = abs(t_)
    if np.sign(s_)*np.sign(t_) == -1:
        return as_ + at_ + min(as_, at_)
    else:
        return max(as_,at_)


for x in X:
    s_i = bisect.bisect_left(s,x)
    t_i = bisect.bisect_left(t,x)
    s_l = s[s_i-1]
    s_r = s[s_i]
    t_l = t[t_i-1]
    t_r = t[t_i]
    ans = dec(x,s_l,t_l)
    ans_ = dec(x,s_l,t_r)
    if ans > ans_:
        ans = ans_
    ans_ = dec(x,s_r,t_l)
    if ans > ans_:
        ans = ans_
    ans_ = dec(x,s_r,t_r)
    if ans > ans_:
        ans = ans_
    print(ans)




### FIXED CODE ###

A,B,Q=list(map(int,input().split()))
s=[0]*(A+2)
t=[0]*(B+2)
X=[0]*Q
s[0] = -float('inf')
s[A+1] = float('inf')
t[0] = -float('inf')
t[B+1] = float('inf')
for i in range(1,A+1):
    s[i] = int(input())
for i in range(1,B+1):
    t[i] = int(input())
for i in range(Q):
    X[i] = int(input())

import bisect

for x in X:
    s_i = bisect.bisect_left(s,x)
    t_i = bisect.bisect_left(t,x)
    s_l = abs(s[s_i-1]-x)
    s_r = s[s_i]-x
    t_l = abs(t[t_i-1]-x)
    t_r = t[t_i]-x
    ans = min([max(s_l,t_l),s_l+t_r+min(s_l,t_r),s_r+t_l+min(s_r,t_l),max(s_r,t_r)])

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

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
cnt = 0
ans = 0


for i in range(N - 1):

    if ans > N - i:
        break

    else:
        for j in range(i, N - 1):

            if H[j] >= H[j + 1]:
                cnt += 1
            else:
                break

    if ans < cnt:
        ans = cnt
    cnt = 0

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        cnt += 1
    else:
        ans.append(cnt)
        cnt = 0

ans.append(cnt)
print(max(ans))
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] > ds[y][x] + 1:
                ds[ny][nx] = ds[y][x] + 1
                q.append([nx, ny])


q = [[0, 0]]
while q:
    x, y = q.pop()
    bfs(x, y)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] > ds[y][x] + 1:
                ds[ny][nx] = ds[y][x] + 1
                dfs(nx, ny)


dfs(0, 0)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)
### BUGGY CODE ###

N, P = map(int, input().split())
ret = 1
k = 0
r = 2

while P != 1:
    if P % r == 0:
        k += 1
        P /= r
        if k == N:
            ret *= r
            k = 0
    else:
        k = 0
        if r == 2:
            r += 1
        else:
            r += 2

print(ret)

### FIXED CODE ###

N, P = map(int, input().split())

if N == 1:
    print(P)
    exit()

div = 2
res = 1
R = P

while div * div <= R and div <= P:
    cnt = 0
    while P % div == 0:
        P /= div
        cnt += 1

        if cnt == N:
            res *= div
            cnt = 0
    div += 1

print(res)
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
seq_s = "".join(s)
ans = 0
start_i = 0
used_s = {}
for i in range(n):
    cnt = used_s.get(s[i],seq_s.count(s[i],start_i))
    ans += cnt - 1
    used_s[s[i]] = cnt - 1
    start_i += len(s[i])

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = "".join(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

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

s = input()
while 1:
    s1 = s.replace('ST','',1)
    if len(s1) == len(s):
        break
    s = s1
print(str(len(s1)) + "\n")


### FIXED CODE ###

st = input()
sc = 0
tc = 0
for s in st:
    if s == "S":
        sc += 1
    if s == "T":
        if sc > 0:
            sc -= 1
        else:
            tc += 1

print(sc + tc)
### BUGGY CODE ###

import sys

lines = sys.stdin.readlines()
n = int( lines[0] )
eles = []
for i in range( 1, n+1 ):
	op = lines[i].rstrip().split( " " )
	if "insert" == op[0]:
		eles.insert( 0, op[1] )
	elif "delete" == op[0]:
		if op[1] in eles:
			eles.remove( op[1] )
	elif "deleteFirst" == op[0] :
		eles.pop( 0 )
	elif "deleteLast" == op[0]:
		eles.pop( )

print( " ".join( eles ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


print( " ".join( que ) )
### BUGGY CODE ###

def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = 0
    b_stock = 0
    s = list(s)
    while index < len(s):
        si = s[index]
        # print(index)
        # print(si)
        # print(a_stock)
        # print(b_stock)
        # print(ope_num)
        # print()
        if si == "A":
            b_stock = 0
            a_stock = 1
        elif a_stock > 0:
            if si == "B" and b_stock == 0:
                b_stock = 1
            elif si == "C" and b_stock > 0:
                ope_num = ope_num + 1
                s[index - 2] = "B"
                s[index - 1] = "C"
                s[index] = "A"
                a_stock = 0
                b_stock = 0
                if index - 4 >= -1:
                    index = index - 4
                else:
                    index = index - 1
            else:
                a_stock = 0
                b_stock = 0
        else:
            a_stock = 0
            b_stock = 0
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する


### FIXED CODE ###

def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = 0
    b_stock = 0
    s = list(s)
    while index < len(s):
        # print(s)
        # print(index)
        # print(ope_num)
        # print()
        si = s[index]
        if si == "A":
            if b_stock > 0:
                a_stock = 1
            else:
                a_stock = a_stock + 1
            b_stock = 0
        elif a_stock > 0:
            if b_stock == 0:
                if si == "B":
                    b_stock = 1
                else:
                    a_stock = 0
                    b_stock = 0
            elif si == "C":
                ope_num = ope_num + a_stock
                # s[index - 2 - a_stock + 1] = "B"
                # s[index - 1 - a_stock + 1] = "C"
                # s[index] = "A"
                # index = index - 1
                a_stock = a_stock
                b_stock = 0
            else:
                a_stock = 0
                b_stock = 0
        else:
            a_stock = 0
            b_stock = 0
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
len_s = len(s)

for i in range(len_s):
    for j in range(i+1, len_s):
        for k in range(j+1, len_s):
            if (s[i] != s[j] and s[i] != s[k] and s[j] != s[k]) and (j-i != k-j):
                ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1, n-1):
        k = 2 * j - i
        if(k < n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1

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

import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, read().split())
    s = [[False] * w] + [[False] + [i == "." for i in read()] + [False] for _ in range(h)] + [[False] * w]
    left = [[0] * (w + 2) for _ in range(h + 2)]
    right = [[0] * (w + 2) for _ in range(h + 2)]
    up = [[0] * (w + 2) for _ in range(h + 2)]
    down = [[0] * (w + 2) for _ in range(h + 2)]
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if s[y][x]:
                left[y][x] = left[y][x - 1] + 1
                up[y][x] = up[y - 1][x] + 1
            if s[-y - 1][-x - 1]:
                right[-y - 1][-x - 1] = right[-y - 1][-x] + 1
                down[-y - 1][-x - 1] = down[-y][-x - 1] + 1
    c = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if s[y][x]:
                c = max(left[y][x] + right[y][x] + up[y][x] + down[y][x], c)
    print(c - 3)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    h, w = map(int, read().split())
    s = [list(read()) for _ in range(h)]
    row = [[0 for _ in range(w)] for _ in range(h)]
    col = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        c = 0
        for j in range(w):
            if s[i][j] == "#":
                for k in range(j - c, j):
                    row[i][k] = c
                c = 0
            else:
                c += 1
        for k in range(w - c, w):
            row[i][k] = c
    for i in range(w):
        c = 0
        for j in range(h):
            if s[j][i] == "#":
                for k in range(j - c, j):
                    col[k][i] = c
                c = 0
            else:
                c += 1
        for k in range(h - c, h):
            col[k][i] = c
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(row[i][j] + col[i][j], ans)
    print(ans - 1)

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

import sys
import numpy as np

input = lambda: sys.stdin.readline().rstrip()

def solve(a):
    # a_max = max(a)
    # idx_max = a.index(a_max)
    idx_max = a.argmax()
    a_max = a[idx_max]
    return ((len(a) - 1 - idx_max) * a_max) - sum(a[idx_max + 1:]), idx_max

def solve2(a):
    idx_min = 0
    sum_a = 0
    for i in range(1, len(a)):
        if a[0] < a[i]:
            return ((i - 1) * a[0]) - sum_a, i
        else:
            sum_a += a[i]
            if i == len(a) - 1:
                return (i * a[0]) - sum_a, i + 1

def main():
    n = int(input())
    a = np.array(list(map(int, input().split())))
    ans = 0
    while(1):
        k, idx_max = solve(a)
        ans += k
        if idx_max == 0:
            break
        a = a[:idx_max]
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    idx_start = 0
    sum_a = 0
    ans = 0
    cnt = 0
    len_a = len(a)

    for i in range(1, len_a):
        if a[idx_start] < a[i]:
            ans += (cnt * a[idx_start]) - sum_a
            idx_start = i
            sum_a = 0
            cnt = 0
        else:
            sum_a += a[i]
            cnt += 1
            if i == len_a - 1:
                ans += (cnt * a[idx_start]) - sum_a
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter 
import math

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

N = int(input())
A = list(map(int,input().split()))
P = list(set(A))
tmp = Counter(A)
tmp2 = tmp.most_common()
li = [list(tmp2[i]) for i in range(len(tmp2))]
P.sort()
li.sort()
S = sum(comb(li[i][1],2) for i in range(len(li)) if li[i][1]>=2)
for i in A:
    ans = S
    IDX = P.index(i)
    if li[IDX][1]>2:
        ans -= comb(li[IDX][1],2)-comb(li[IDX][1]-1,2)
    elif li[IDX][1]==2:
        ans -= 1
    print(ans)

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

N = int(input())
A = list(map(int,input().split()))
li = Counter(A)
S = 0
for i,j in enumerate(li):
    if li[j]>=2:
        S += comb(li[j],2)

for i in A:
    ans = S
    tmp = li[i]
    if tmp>2:
        ans -= comb(tmp,2)-comb(tmp-1,2)
    elif tmp==2:
        ans -= 1
    print(ans)
### BUGGY CODE ###

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

ans = 1
can = 1
zero = 0

for i in range(N):
    if a[i]==0:
        zero = 1
        ans = 0

if(zero==0):
    for i in range(N):
        ans = ans * a[i]
        if(ans>1000000000000000000):
            can = 0

if(can==1):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

ans = 1
can = 1
zero = 0

if 0 in a:
    zero = 1
    ans = 0

if(zero==0):
    for i in range(N):
        ans = ans * a[i]
        if(ans>1000000000000000000):
            can = 0
            break

if(can==1):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
a = int(input())
b,c=map(int,input().split())
while(True):
    for i in range(a, b+1):
        if i//a == 0:
            print('True')
            break
    print('NG')
print('OK')




### FIXED CODE ###

import numpy as np
a = int(input())
b,c=map(int,input().split())
d = np.arange(a,1001,a)
f = np.arange(b,c+1)
d_set=set(d)
f_set=set(f)
#dとfに共通するものを抽出
g_set=d_set&f_set 
#結果をlistに変換
g=list(g_set)
if len(g) == 0:
    print('NG')
else:
    print('OK')