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

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
H = LI()

INF = 10 ** 10


def main():
    dp = [INF] * N
    dp[0] = 0
    for i in range(1, N):
        n = min(K + 1, i + 1)
        for j in range(1, n):
            dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
H = LI()

INF = 10 ** 10


def main():
    dp = [INF] * N
    dp[0] = 0
    for i in range(1, N):
        n = min(K + 1, i + 1)
        for j in range(1, n):
            dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    ans = dp[-1]
    print(ans)


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

x=int(input())
c=1
for b in range(1,x):
    for p in range(2,x):
        if b**p<=x:c=max(c,b**p)
print(c)

### FIXED CODE ###

import math 
x = int(input())
ans = 0

if x ==1:
  print(1)
  
else:
  for i in range(1,x//2):
    for j in range(2,11):
      tmp = i **j
      if tmp <= x:
        ans = max(ans,tmp)
        
  print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
#S = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]
S = [input() for _ in range(H)]

cost = [[10000]*W for _ in range(H)]

def dfs(i, j, c):
  if i >= H or j >= W:
    return
  else:
    cost[i][j] = min(cost[i][j], c+1 if S[i][j]=='#' else c)
    dfs(i+1, j, cost[i][j])
    dfs(i, j+1, cost[i][j])

dfs(0, 0, 0)
print(cost[-1][-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
cost = [[0]*W for _ in range(H)]
cost[0][0] = 1 if S[0][0] == '#' else 0
for w in range(1,W):
  if S[0][w-1] == '.' and S[0][w] == '#':
    cost[0][w] = cost[0][w-1] + 1
  else:
    cost[0][w] = cost[0][w-1]
for h in range(1,H):
  if S[h-1][0] == '.' and S[h][0] == '#':
    cost[h][0] = cost[h-1][0] + 1
  else:
    cost[h][0] = cost[h-1][0]

for h in range(1,H):
  for w in range(1,W):
    if S[h-1][w] == '.' and S[h][w] == '#':
      ch = cost[h-1][w] + 1
    else:
      ch = cost[h-1][w]
    if S[h][w-1] == '.' and S[h][w] == '#':
      cw = cost[h][w-1] + 1
    else:
      cw = cost[h][w-1]
    cost[h][w] = min(ch, cw)

print(cost[-1][-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])
 
edges=[[] for i in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i != j:
            edges[i].append((dd(v[i],v[j]),j))
            edges[j].append((dd(v[i],v[j]),i))
 
def dijkstra(s,n,edges):
    #edges[source] = [(cost_1,target_1),(cost_2,target_2),...]
    #import 'heap'
    d = [float('inf')] * n
    d[s] = 0
    q = [[d[s],s]]
    while q:
        dist_u, u = heappop(q)
        for c, v in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q,[d[v],v])
    return d
 
ans = dijkstra(0,n+2,edges)
print(ans[n+1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(i+1,n+2):
        edges[i][j] = dd(v[i],v[j])
        edges[j][i] = dd(v[i],v[j])

def dijkstra(s,n,edges):
    #edges[i][j] : the cost of i→j
    #import 'heap'
    d = [float('inf') for _ in range(n)]
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])
### BUGGY CODE ###

def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        c = sieve(100000)
        print(solve(l,r,c))

### FIXED CODE ###

def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    c = sieve(100000)
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r,c))
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

from itertools import combinations
import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))

N,M,K = map(int,input().split())
ans = 0
mod = 10**9 +7
by = choose(N*M-2,K-2)

#まずは、X軸の総和を求める。
X = []
for i in range(1,N+1):
    for j in range(M):
        X.append(i)

for a,b in list(combinations(X,2)):
    ans = (ans + abs(a-b)*by%mod)%mod


Y = []
for i in range(1,M+1):
    for j in range(N):
        Y.append(i)

for a,b in list(combinations(Y,2)):
    ans = (ans + abs(a-b)*by%mod)%mod

print(ans)

### FIXED CODE ###

import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
mod = 10**9 +7
N,M,K = map(int,input().split())
ans = 0
memo = choose(N*M-2,K-2)
memo %= mod
#まずはX軸について、総和を考える
d = 1
while d < M:
    ans += d*memo*(M-d)*N*N
    d += 1
    ans %= mod

#Y軸について、総和を考える
d = 1
while d < N:
    ans += d*memo*(N-d)*M*M
    d += 1
    ans %= mod

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

def main():
    from collections import deque

    h, w, ch, cw, dh, dw, *m, = open(0).read().split()
    h, w = int(h), int(w)
    start = (int(ch) - 1, int(cw) - 1)
    goal = (int(dh) - 1, int(dw) - 1)
    maze = [tuple(list(i)) for i in m]

    vis = set()

    mw = tuple([(1, 0), (0, 1), (-1, 0), (0, -1)])
    mj = tuple(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if (y, x) in vis or maze[y][x] == '#':
            continue
        vis.add((y, x))
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                    continue
                if m[y + s][x + t] == '#':
                    edge.append((y, x))
                    continue
                q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                        continue
                    if vis[y + s][x + t]:
                        continue
                    if m[y + s][x + t] == '#':
                        continue
                    nx += walk(y + s, x + t)
                    if vis[dh][dw]:
                        return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


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

def main():
    def gcd(v1, v2):
        while v2 > 0:
            v1,v2 = v2, v1%v2
        return v1

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

    res = 0
    for a in a_list:
        res = (res + a_lcm // a) % MOD
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###


from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

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

import sys


def main():
    N, M = map(int, input().split())
    s = M // N  # 答えはs以下
    m = M % N

    for i in range(s, 0, -1):
        if m % s == 0:
            print(s)
            sys.exit()
        else:
            s -= 1
            m += N


main()


### FIXED CODE ###

import sys


def main():
    N, M = map(int, input().split())
    s = M // N  # 答えはs以下
    m = M % N

    for i in range(s, 0, -1):
        if m % i == 0:
            print(i)
            sys.exit()
        else:
            m += N


main()
### BUGGY CODE ###

import math

def lcm(x,y):
    return (x*y)//math.gcd(x,y)

A,B,C,D=map(int,input().split())

l=lcm(C,D)

temp=0
for i in range(l):
    if i%C!=0:
        if i%D!=0:
            temp+=1

a=(A-1)%l
b=B%l

aa=(A-1)//l
bb=B//l

tempA=0
tempB=0

for j in range(a+1):
    if j%C!=0:
        if j%D!=0:
            tempA+=1
            
for k in range(b+1):
    if k%C!=0:
        if k%D!=0:
            tempB+=1

ans=temp*bb+tempB-(temp*aa+tempA)

print(ans)


### FIXED CODE ###

import math

def lcm(x,y):
    return (x*y)//math.gcd(x,y)

A,B,C,D=map(int,input().split())

l=lcm(C,D)

temp=l-(l//C+l//D-1)

a=(A-1)%l
b=B%l

aa=(A-1)//l
bb=B//l

tempA=a-(a//C+a//D-1)
tempB=b-(b//C+b//D-1)
            

ans=temp*bb+tempB-(temp*aa+tempA)


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

N, Q= map(int, input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)] 

T = "AC"

for val in range(len(lr)):
	lr_part = S[lr[val][0]-1:lr[val][1]]

	counter = 0
	for i in range(0, len(lr_part)-1):
		if lr_part[i] + lr_part[i+1] == T:
			counter += 1

	print(counter)

### FIXED CODE ###

N, Q= map(int, input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)] 

T = "AC"
t = [0] * (N+1)

for val in range(N):
	if S[val:val+2] == "AC":
		t[val + 1] = t[val] + 1
	else:
		t[val + 1] = t[val]

for val in range(Q):

	print(t[lr[val][1]-1] - t[lr[val][0]-1])
### BUGGY CODE ###

import collections
# from collections import OrderedDict

N = int(input())
S = [input() for _ in range(N)]

c = collections.Counter(S)

hoge = []
for k, v in c.items():
    if max(c.values()) == v:
        hoge.append(k)

hoge = sorted(hoge)
for i in hoge:
    print(i)

### FIXED CODE ###

import collections
# from collections import OrderedDict

N = int(input())
S = [input() for _ in range(N)]

c = collections.Counter(S)
max_vale = c.most_common()[0][1]

hoge = []
for k, v in c.items():
    if max_vale == v:
        hoge.append(k)

hoge = sorted(hoge)
for i in hoge:
    print(i)



# for i in c.most_common():
#     print(i)
### BUGGY CODE ###

n = int(input())

divs = []

for i in range(n + 1):
  if i == 0:
    continue
  mod = n % i
  if mod == 0:
    divs.append(i)

center = int(len(divs) / 2)
print(divs[center-1] + divs[center] -2)

### FIXED CODE ###

n = int(input())

divs = []

for i in range(1, int(n**0.5)+1):
  if n % i == 0:
      divs.append(i)
      divs.append(n // i)

max = len(divs) -1
print(divs[max] + divs[max-1] - 2)
### BUGGY CODE ###

def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    
    p=x[0][0]
    tmp=[ x[0][j] for j in range(1,w)]
    for i in range(1,h):
        tmp+=x[i]
    tmp.sort(reverse=True)
    
    L=p+sum(tmp[:h+w-2])+1
    
    state=[[[0 for k in range(L)] for j in range(w)] for i in range(h)]


    state[0][0][p]=1

    for j in range(1,w):
        p=x[0][j]
        for k in range(L):
            if state[0][j-1][k]==1:
                state[0][j][k+p]=1
                state[0][j][abs(k-p)]=1

    for i in range(1,h):
        p=x[i][0]
        for k in range(L):
            if state[i-1][0][k]==1:
                state[i][0][k+p]=1
                state[i][0][abs(k-p)]=1

    for i in range(1,h):
        for j in range(1,w):
            p=x[i][j]
            for k in range(L):
                if state[i-1][j][k]==1 or state[i][j-1][k]==1:
                    state[i][j][k+p],state[i][j][abs(k-p)]=1,1



    for k in range(L):
        if state[h-1][w-1][k]==1:
            print(k)
            break
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    

    L=12800
    
    state=[[0]*w for _ in range(h)]
    delta=x[0][0]
    state[0][0]=(2**L>>delta)|(2**L<<delta)

    for j in range(1,w):
        delta=x[0][j]
        state[0][j]=(state[0][j-1]>>delta)|(state[0][j-1]<<delta)

    for i in range(1,h):
        delta=x[i][0]
        state[i][0]=(state[i-1][0]>>delta)|(state[i-1][0]<<delta)

    for i in range(1,h):
        for j in range(1,w):
            delta=x[i][j]
            state[i][j]=(state[i][j-1]>>delta)|(state[i][j-1]<<delta)
            state[i][j]|=(state[i-1][j]>>delta)|(state[i-1][j]<<delta)

    
    ans = 10**9
    for i in range(L*2):
        if state[h-1][w-1] & 1:
            ans = min(ans,abs(i-L))
        state[h-1][w-1]>>=1
    print(ans)



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

def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * (V+1) for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

### FIXED CODE ###

def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * (V+1) for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
set_A = list(set(A))
set_A.sort(reverse=True)
c = collections.Counter(A)
Max = max(A)
Max_list = [i for i, v in enumerate(A) if v == max(A)]
for i in range(N):
    if A[i] == Max:
            if len(Max_list) > 1:
                print(A[i])
            else:
                print(set_A[1])
    else:
        print(Max)


### FIXED CODE ###

import copy
N = int(input())
A = [int(input()) for i in range(N)]
set_A = list(set(A))
set_A.sort(reverse=True)
A_copy = copy.deepcopy(A)
A_copy.sort(reverse=True)
Max = max(A)
cnt = 0
for i in range(N):
    if A[i] == Max:
        cnt += 1
for i in range(N):
    if A[i] == Max:
        if cnt > 1:
            print(Max)
        else:
            print(set_A[1])
    else:
        print(Max)
### BUGGY CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

s = set(range(LR[0][0], LR[0][1]+1))
for lr in LR:
  s = s.intersection(s, set(range(lr[0], lr[1]+1)))

print(len(s))

### FIXED CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

minv = 100000
maxv = 1
for lr in LR:
  maxv = max(maxv, lr[0])
  minv = min(minv, lr[1])

print(max(0, minv - maxv + 1))
### BUGGY CODE ###

import heapq
N, L, T = map(int, input().split())
X = [0 for i in range(N)]
ant = [[] for i in range(2)]
E = [0 for i in range(N)]
for i in range(N):
    X[i], w = map(int, input().split())
    ant[w-1].append(i)
    if w == 1:
        end = X[i] + T
        end = end % L
    if w == 2:
        end = X[i]-T
        end = end % L
        if end < 0:
            end += L
    E[i] = end
len0 = len(ant[0])
len1 = len(ant[1])
TA = []
for m in range(len0):
    for n in range(len1):
        Y0 = ant[0][m]
        Y1 = ant[1][n]
        sa = X[Y1] - X[Y0]
        if sa < 0:
            sa += L
        gikan = sa / 2.0
        while gikan < T:
            heapq.heappush(TA,(gikan, Y0, Y1))
            gikan += L / 2.0
lastant = [i for i in range(N)]

for i in range(len(TA)):
    time, Y0, Y1 = heapq.heappop(TA)
    a = lastant[Y0]
    b = lastant[Y1]
    lastant[Y0] = b
    lastant[Y1] = a

result = [0 for i in range(N)]
for i in range(N):
    result[lastant[i]] = E[i]
for i in range(N):
    print(result[i])


### FIXED CODE ###

N, L, T = map(int, input().split())
X = [0 for i in range(N)]
W = [0 for i in range(N)]
E = [0 for i in range(N)]
count = 0
for i in range(N):
    X[i], W[i] = map(int, input().split())
    if W[i] == 1:
        end = X[i] + T
        end = end % L
    if W[i] == 2:
        end = X[i]-T
        end = end % L
        if end < 0:
            end += L
    E[i] = end
    shu = L / 2.0
    if i > 0 and W[i] == 2 and  W[0] == 1:
        sa = X[i] -X[0]
        if sa < 0:
            sa += L
        gikan = sa / 2.0
        count += (T - gikan ) // shu + 1
        if (T - gikan) % shu == 0:
            count -= 1

    if i > 0 and W[i] == 1 and  W[0] == 2:
        sa = X[0] -X[i]
        if sa < 0:
            sa += L
        gikan = sa / 2.0
        count -= (T - gikan ) // shu + 1

#print(E)
count = count % N
if count < 0:
    count += N
count = int(count)
#print(count)
basho = E[0]
E.sort()
ind = E.index(basho)
result = [0 for i in range(N)]
for i in range(N):
    newind = ind + i
    if newind >= N :
        newind -= N
    result[count] = E[newind]
    count += 1
    if count >= N:
        count -= N

for i in range(N):
    print(result[i])
### BUGGY CODE ###

s=input()
n=int(s)
m=len(s)
if n<2019:
    print(0)
    exit()
from collections import Counter
c=Counter()
for i in range(m+1):
    c[(n%(10**i))%2019]+=1

ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)


### FIXED CODE ###

s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())
### BUGGY CODE ###

# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)

    return sorted(ans)


def main():
    N = int(input())

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

    # is_in_A_flag = [0] * (10**6+1)
    is_in_A_flag = {f"{i}": 0 for i in range(10**6+1)}

    for a in A:
        is_in_A_flag[f"{a}"] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[f"{b}"] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[f"{B[i][-1]}"] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())


### FIXED CODE ###

# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())