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

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :float("inf"))
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [float('inf') for _ in range(n)]
used = defaultdict(lambda: False)
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	if used[p-1 + t * n] == False:
		edges[p-1 + t * n].append([p-1 + 0 * n, 0])
		edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	if used[q-1 + t * n] == False:
		edges[q-1 + t * n].append([q-1 + 0 * n, 0])
		edges[q-1 + 0 * n].append([q-1 + t * n, 1])
	used[p-1 + t * n] = True
	used[q-1 + t * n] = True

#print(edges.items())
d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res == float("inf"):
	print(-1)
else:
	print(res)

### FIXED CODE ###

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])
nxt_st_all = set([])

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)
### BUGGY CODE ###


n= int(input())
l=[0]+list(map(int,input().split()))

d=[0]*(n+1)
for i in range(1,n+1):
    for k in range(i+1,n+1):
        if k-i==l[k]+l[i]:
            d[k-i]+=1
print(sum(d))

### FIXED CODE ###

n= int(input())
l=list(map(int,input().split()))
d={}
ans=0
for i in range(n):
    
    if i-l[i] in d:
        ans+=d[i-l[i]]
    if i+l[i] in d:
        d[i+l[i]]+=1
    else:
        d[i+l[i]]=1
print(ans)
### BUGGY CODE ###

def comb(n, r):
    bunshi = 1
    for i in range(n-r+1,n+1):
        bunshi = bunshi*i
    bunbo = 1
    for i in range(1,r+1):
        bunbo = bunbo * i 
    return bunshi//bunbo

def pascal(n):
    c = [[0 for i in range(n+1)] for j in range(n+1)]
    c[0][0] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j == 0 or j == i:
                c[i][j] = 1
                continue
            c[i][j] = c[i-1][j-1] +c[i-1][j]
    return(c)

def nC2(n):
    c = [0 for _ in range(n)]
    c[0] = 1
    for i in range(1, n):
        c[i] = i+1 +c[i-1]
    return(c)

N = int(input())
A = list(map(int, input().split()))
# c = pascal(N)
# nc2 = nC2(N)
duplication = {}
ans = 0
for x in A:
    if x in duplication:
        continue
    count = A.count(x)
    if count > 1:
        duplication[x] = count
        # ans += comb(count,2)
        # ans += nc2[count-2]
        for i in range(count):
            ans += i
for x in A:
    if x not in duplication:
        print(ans)
    else:
        # print(ans -comb(duplication[x],2) +comb(duplication[x]-1,2))
        print(ans -duplication[x]+1)
        # print(ans -c[duplication[x]][2] +c[duplication[x]-1][2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
def test():
    duplication = {}
    ans = 0
    for x in A:
        if x in duplication:
            continue
        count = A.count(x)
        if count > 1:
            duplication[x] = count
            ans += count*(count-1)//2
    for x in A:
        if x not in duplication:
            print(ans)
        else:
            print(ans -(duplication[x]-1))
from collections import defaultdict

sum = 0
count_dic = defaultdict(int)
for x in A:
    count_dic[x] +=1
for v in count_dic.values():
    sum += v*(v-1)//2
for x in A:
    print(sum -(count_dic[x]-1))
### BUGGY CODE ###

import sys
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
def query():
    p = b_num-1
    q = n+b_num-2
    res=mx
    while q-p>1:
        if p&1 == 0:
            res = min(res,segl[p])
        if q&1 == 1:
            res = min(res,segl[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,segl[p])
    else:
        res = min(min(res,segl[p]),segl[q])
    return res

input = sys.stdin.readline

xs = []
for i in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
for _ in range(Q):
    xs.append((int(input()),2))
xs.sort(key=lambda x:x[0])

for x in xs:
    if x[1]==2:
        c = query()
        print(c if c!= mx else -1)
        continue
    update(x[3], x[2] if x[1] else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

def BFS(H, W, grid):
    visited = [[False for _ in range(W)] for _ in range(H)]
    que = deque()
    for i in range(H):
        for j in range(W):
            if(grid[i][j] == "#"):
                que.append((i, j, 0))
    dist = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        
    while que:
        x, y, c = que.popleft()
        visited[x][y] = True
        
        for dx, dy in dist:
            nx = x + dx
            ny = y + dy
            
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            if(not visited[nx][ny]):
                que.append((nx, ny, c+1))
    return c
        
print(BFS(H, W, grid))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

def BFS(H, W, grid):
    visited = [[True for _ in range(W+2)] for _ in range(H+2)]
    que = deque()
    for i in range(H):
        visited[i+1][1:-1] = map(lambda _:_=="#", grid[i])
        for j in range(W):
            if(grid[i][j] == "#"):
                que.append((i+1, j+1, 0))
    dist = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        
    while que:
        x, y, c = que.popleft()
        for dx, dy in dist:
            nx = x + dx
            ny = y + dy
            
            if(not visited[nx][ny]):
                que.append((nx, ny, c+1))
                visited[nx][ny] = True
    return c
        
print(BFS(H, W, grid))
### BUGGY CODE ###

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
to = [[] for i in range(n+1)]
cnt = [0] * (n+1)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
for i in range(1,n+1):
    print(cnt[i] , end =" ")


### FIXED CODE ###

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)

to = [[] for i in range(n+1)]
cnt = [0] * (n)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p-1] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
print(*cnt)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = [a.pop(0)]
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.insert(0,ai)
print(len(color))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
from collections import Counter
from operator import itemgetter
 
l = Counter(A).most_common()
l = [[a, b] for a, b in l]
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    l = [[a, b] for a, b in l]
    while l[K][1] > 0:
        for i in range(K+1):
            l[i][1] -= 1
        l.sort(key = itemgetter(1), reverse = True)
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

ken = {p[0] for p in PY}
ken_d = {k:[] for k in ken}

for p in PY:
    # print(p)
    ken_d[p[0]].append(p[1])

for k in ken_d.keys():
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))


### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

from collections import deque
K = int(input())

q = deque([1])
used = [False] * K
def cost(x):
    ret = 0
    while x:
        ret += x % 10
        x //= 10
    return ret

while True:
    x = q.popleft()
    if x % K == 0:
        print(cost(x))
        break
    elif used[x % K]:
        continue
    used[x % K] = True
    if (x+1) % 10 == 0:
        q.appendleft(x+1)
    else:
        q.append(x+1)
    q.appendleft(10*x)


### FIXED CODE ###

from collections import deque
K = int(input())

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if k % K == 0:
        print(x)
        break
    if (x, 0, k*10%K) in used:
        continue
    else:
        used.add((x, 0, k*10%K))
    q.appendleft((x, 0, k*10%K))
    if (y + 1) % 10 == 0:
        q.appendleft((x, 0, k+1))
    else:
        q.append((x+1, y+1, k+1))
### BUGGY CODE ###

s = list(input())
l = len(s)
ans = 0
for i in range(l):
    if s[i] == "W":
        ans += s[:i].count("B")
print(ans)

### FIXED CODE ###

s = list(input())
ans = 0
cnt =0
for i in s:
    if i == "B":
        cnt += 1
    else:
        ans += cnt
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))
pl_i = []
pl_max = 0
s = 0
for i in range(n):
    for j in range(1, pl[i]+1):
        s += j
    pl_i.append(s / pl[i])
    s = 0
for m in range(n - k + 1):
    pl_max = max(pl_max, sum(pl_i[m:m + k]))
print(pl_max)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
res = tmp
for i in range(n - k):
    tmp -= p[i]
    tmp += p[i + k]
    res = max(res, tmp)
print((res + k) / 2)
### BUGGY CODE ###

import bisect

def main():
    n, *l = map(int, open(0).read().split())
    l.sort()

    ans = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            # a = l[i], b = l[j], c = ?
            # c < a + b
            # max_c = a + b - 1
            # abs(a - b) < c
            # min_c = abs(a - b) + 1
            a = l[i]
            b = l[j]
            c = l[j+1:]
            max_c = bisect.bisect_right(c, a + b - 1)
            min_c = bisect.bisect_left(c, abs(a - b + 1))
            ans += max_c - min_c
    print(ans)
    return()

if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect

def main():
    n, *l = map(int, open(0).read().split())
    l = sorted(l, reverse=True)

    ans = 0
    for a_i in range(n-2):
        a = l[a_i]
        b_i = a_i + 1
        c_i = n - 1
        while b_i < c_i:
            b = l[b_i]
            c = l[c_i]
            if a < b + c:
                b_i += 1
                ans += c_i - b_i + 1
            else:
                c_i -= 1
    print(ans)
    return()

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

H,W,K = list(map(int,input().split()))
C = [list(input()) for _ in range(H)]

def F1(c):
    for i in range(W):
        for j in range(H-1,-1,-1):
            if c[j][i] != 'X': continue
            for k in range(j-1,-1,-1):
                if c[k][i] != 'X':
                    c[j][i], c[k][i] = c[k][i], c[j][i]
                    break
    return c

def F2(c):
    delete_sum = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == 'X': continue
            tmp = c[i][j]
            count = 1
            for k in range(j+1,W):
                if c[i][k] == tmp:
                    count += 1
                else:
                    break
            if count >= K:
                for k in range(j,W):
                    if c[i][k] == tmp:
                        delete_sum += int(c[i][k])
                        c[i][k] = 'X'
                    else:
                        break
    return c, delete_sum

MAX = 0
for i in range(H):
    for j in range(W):
        tmpC = []
        for k in range(H):
            tmpC.append(C[k][:])
        tmpC[i][j] = 'X'
        tmpC = F1(tmpC)
        point = 0
        for k in range(1000):
            tmpC, delete_sum = F2(tmpC)
            if delete_sum == 0:
                break
            tmpC = F1(tmpC)
            point += 2**k*delete_sum
        MAX = max(MAX,point)
print(MAX)

### FIXED CODE ###

H,W,K = list(map(int,input().split()))
C = [list(input()) for _ in range(H)]

def F1(c):
    for i in range(W):
        for j in range(H-1,-1,-1):
            if c[j][i] != 'X': continue
            for k in range(j-1,-1,-1):
                if c[k][i] != 'X':
                    c[j][i], c[k][i] = c[k][i], c[j][i]
                    break
    return c

def F2(c):
    delete_sum = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == 'X': continue
            tmp = c[i][j]
            count = 1
            for k in range(j+1,W):
                if c[i][k] == tmp:
                    count += 1
                else:
                    break
            if count >= K:
                for k in range(j,W):
                    if c[i][k] == tmp:
                        delete_sum += int(c[i][k])
                        c[i][k] = 'X'
                    else:
                        break
    return c, delete_sum

MAX = 0
for i in range(H):
    for j in range(W):
        tmpC = []
        for k in range(H):
            tmpC.append(C[k][:])
        tmpC[i][j] = 'X'
        tmpC = F1(tmpC)
        point = 0
        for k in range(1000):
            tmpC, delete_sum = F2(tmpC)
            if delete_sum == 0:
                break
            tmpC = F1(tmpC)
            point += 2**k*delete_sum
        MAX = max(MAX,point)
print(MAX)
### BUGGY CODE ###

N = int(input())
arr = [int(input()) for i in range(N)]
max_v= []
for v in arr:
  check = 0
  for i, k in enumerate(max_v):
    if k < v:
      max_v[i] = v
      check = 1
      break
  if check == 0:
    max_v.append(v)
print(len(max_v))


### FIXED CODE ###

import bisect
N = int(input())
arr = [int(input()) for i in range(N)]
dp = [-1 for _ in range(N)]
for i in arr:
    dp[bisect.bisect_left(dp, i) - 1] = i
print(sum([i >= 0 for i in dp]))
### BUGGY CODE ###

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

com_sum = [0] * (N+1)
for i in range(N):
    com_sum[i+1] = A[i] + com_sum[i]
ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        if (com_sum[j] - com_sum[i]) % M == 0:
            ans += 1
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
import collections
mod_table=collections.defaultdict(int)
com_sum = [0] * (N+1)
for i in range(N):
    com_sum[i+1] = A[i] + com_sum[i]
ans = 0
for i in range(N+1):
    mod = com_sum[i] % M
    mod_table[mod]+=1
    
for x in mod_table:
  y = mod_table[x]
  if y > 1:
    ans += y*(y-1)//2

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

# import sympy
from collections import defaultdict, Counter
# def factors(N): #約数を全て求める。ただし、順不同
#     from collections import deque
#     ret = deque()
#     middle = int( N**(1/2))
#     for i in range(1, middle):
#         if N%i == 0:
#             ret.append(i)
#             ret.append(N//i)
            
#     if N%middle == 0:
#         ret.append(middle)
#         if middle != N//middle:
#             ret.append(N//middle)
#     return ret

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

    divisors.sort()
    return divisors


def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if CA[a] > 1:
            continue
        for p in make_divisors(a):
            if p == a:
                continue
            if d[p]:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter, defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    T = [False]*(10**6+1)
    A.sort()
    Z = [False]*(10**6+1)
    ans = 0
    for a in A:
        if CA[a] == 1 and not T[a]:
            ans += 1
        if not Z[a]:
            Z[a] = True
            for i in range(1, 10**6+1):
                if i*a > 10**6:
                    break
                T[i*a] = True
    print(ans)
if __name__ == '__main__':
    main()