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

import sys
input = sys.stdin.readline
s = input().rstrip("\n")
t = input().rstrip("\n")
dic = {"a":[],"b":[],"c":[],"d":[],"e":[],"f":[],"g":[],"h":[],"i":[],"j":[],"k":[],"l":[],"m":[],"n":[],"o":[],"p":[],"q":[],"r":[],"s":[],"t":[],"u":[],"v":[],"w":[],"x":[],"y":[],"z":[]}
for i,c in enumerate(s):
    dic[c] += [i]
#print(dic)
cnt = 0
ind = -1
ans = 0
for c in t:
    d = dic[c]
#    print("c=",c,"d=",d)
    for i in d: #iは各文字のindex 昇順
#        print("i=",i)
        if ind < i: #もし現在位置<iなら
            ind = i
#            print("found, ind=",i)
            break
    else:
#        print("not found")
        cnt += 1
        ind = -1
        # もう一度
        for j in d :  # jは各文字のindex 昇順
#            print("2周目i=", i)
            if ind < j :  # もし現在位置<iなら
                ind = j
#                print("2周目found, ind=", j)
                break
        else:
#            print("!!!!!!!!!!!!!")
            ans = -1
            break
print(cnt*len(s)+ind+1 if ans > -1 else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
import bisect

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    #print("c=",c,"d[c]=",d[c])
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     #   print("ins=",ins,end = "")
    else:
      #  print("追加",end = "")
        ans += len(s)
        ind = d[c][0]
    #print("ind=", ind)
    #print()
else:
    ans += ind+1

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

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for i in range(m):
	p,q=pq[i][0],pq[i][1]
	res[p-1]+=q
for i in range(n-1):
	a,b=ab[i][0],ab[i][1]
	res[b-1]+=res[a-1]
ans=[]
for i in range(n):
	ans.append(str(res[i]))
print(" ".join(ans))

### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab2=sorted(ab, key=lambda x:x[0])
pq2=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq2:
	res[p-1]+=q
for a,b in ab2:
	res[b-1]+=res[a-1]
ans=str(res[0])
for i in range(1,n):
	ans+=" "+(str(res[i]))
print(ans)
### BUGGY CODE ###

from collections import deque

n,q = map(int,input().split())
graph = [[] for i in range(n)]
cnt = [0] * n

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append(b)

for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x
    que = deque(graph[p])
    while que:
        c = que.popleft()
        cnt[c] += x
        que += deque(graph[c])       

print(str(cnt).replace('[','').replace(']','').replace(',',''))


### FIXED CODE ###

from collections import deque
def main():
    n,q = map(int,input().split())
    values = [0]*n
    links = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = map(int,input().split())
        links[a-1].append(b-1)
        links[b-1].append(a-1)
    
    for _ in range(q):
        p,x = map(int,input().split())
        values[p-1] += x
    d = deque()
    d.append((0,-1))
    
    while len(d) != 0:
        i,p = d.popleft()
        for j in links[i]:
            if j==p:
                continue
            values[j] += values[i]
            d.append((j,i))
    print(*values)
    
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
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)

    return divisors

def solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = {}
    ans = 0
    for a in A:
        divs = make_divisors(a)
        for d in divs:
            if memo.get(d, -1) != -1:
                break
        else:
            ans += cost[a]
        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
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)

    return divisors

def solve():
    N = II()
    A = LI()

    mx = max(A)

    memo = [0] * (mx + 1)
    for a in A:
        for i in range(a, mx+1, a):
            memo[i] += 1
    # print(memo)

    ans = 0
    for a in A:
        if memo[a] == 1:
            ans += 1
    print(ans)

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

MOD = 10**9+7
n = input()
a = list(map(int, input().split()))
ans = 0
for i, ai in enumerate(a):
  if i == len(a)-1:
    continue
  for aj in a[i+1:]:
    ans += ((ai%MOD)*(aj%MOD))%MOD

print(ans%MOD)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
n = input()
a = list(map(int, input().split()))
ans = 0
cum_a = np.cumsum(a[::-1])
cum_a = cum_a[::-1]
for i, ai in enumerate(a):
  if i == len(a)-1:
    continue
  sum_aj = cum_a[i+1]
  ans += ((ai%MOD)*(sum_aj%MOD))%MOD

print(ans%MOD)
### BUGGY CODE ###

N = int(input())
p = list(map(float, input().split()))
dp = [[float(0)] * (N+1) for _ in range(N)]
ans = float(0)
s = N//2+1

dp[0][1] = float(p[0])
dp[0][0] = float(1-p[0])

for i in range(1,N):
    for j in range(i+2):
        if j>0:
            dp[i][j] += dp[i-1][j-1]*p[i]
        if i>0:
            dp[i][j] += dp[i-1][j]*(1-p[i])

for i in range(s,N+1):
    ans += dp[N-1][i]

print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))
dp = [[float(0)] * (N+1) for _ in range(N)]
ans = float(0)
s = N//2+1

dp[0][1] = float(p[0])
dp[0][0] = float(1-p[0])

for i in range(1,N):
    for j in range(i+2):
        if j>0:
            dp[i][j] += dp[i-1][j-1]*p[i]
        if i>0:
            dp[i][j] += dp[i-1][j]*(1-p[i])

for i in range(s,N+1):
    ans += dp[N-1][i]

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

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    rl = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        rl[i] = (r, l, i)
    rl.sort()
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for r, l, i in rl:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    print(*ans, sep='\n')
            
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    trans_a = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    trans_b = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + trans_a]

    q = deque([])
    q.append((c_h-1, c_w-1))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y = q.popleft()

        for dx, dy in trans_a:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                q.appendleft((nx, ny))#ここを変更
                dp[nx][ny] = dp[x][y]#ここを変更

        for dxb, dyb in trans_b:
            nx2, ny2 = x + dxb, y + dyb
            if 0 <= nx2 < h and 0 <= ny2 < w and s[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                q.append((nx2, ny2))
                dp[nx2][ny2] = dp[x][y] + 1

    answer = dp[d_h-1][d_w-1]

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

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

def main():
    n, m, k = map(int, read().split())
    friend = [set() for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] |= pf
    print(*[len(potential[i] - friend[i] - block[i] - {i}) for i in range(n)])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

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

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i]) - len(block[i] & potential[i]) - len(friend[i]) - 1 for i in range(n)])

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

import math
from functools import reduce

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

K = int(input())
ans = 0

for i in range(1,K+1):
  for j  in range(1, K+1):
    for k  in range(1, K+1):
      ans += gcd(i, j, k)

print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    ij = math.gcd(i, j)
    for k in range(1,K+1):
      ans += math.gcd(ij, k)

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

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = sum([1 << (i - 1) for i in map(int, input().split())])
    keys.append([a, bits])

dp = [INF] * (2 ** N + 10)
dp[0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[j|keys[i][1]] = min(dp[j|keys[i][1]], dp[j]+keys[i][0])
print(dp[2 ** N - 1] if dp[2 ** N - 1] != INF else -1)

### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
K = INT()

subs = set()
for i in range(N):
    for j in range(i+1, N+1):
        subs.add(S[i:j])

subs = sorted(subs)
print(subs[K-1])


### FIXED CODE ###

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

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(i, len(instr)+1):
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		if i < j:
			str_list.append(instr[i:j])

		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from itertools import chain
from collections import Counter

def floyd_warshall(V, dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]                # dist は頂点 k までを経由した場合の最短距離。dist[i][k]は k を経由することは無いので、dist[i][k]は k ステップ目で更新されることはない。
                                                                        # よって、min の中身は全て k-1 ステップ目の情報で構成されており、漸化式となっている。
    return dist

##############################
V, X, Y = map(int, input().split())                                        # V:頂点数　E:辺の数

INF = float("inf")                                                      # 10**18 にすると、負のコストがある場合に少し面倒になる

dist = [[INF] * V for _ in range(V)]                                    # 辺が存在しない事をコスト無限大で表現
for k in range(V-1):
    i,j,weight = k, k+1, 1
    # i -= 1                                                            # 番号のデクリメントが必要な場合、コメントアウトを消す
    # j -= 1
    dist[i][j] = weight
    dist[j][i] = weight                                               # 無向グラフの場合はコメントアウトを消す
for i in range(V):
    dist[i][i] = 0                                                      # 自身のところに行くコストは０

dist[X-1][Y-1] = 1
dist[Y-1][X-1] = 1

d = floyd_warshall(V, dist)                                                # 各点間の距離が隣接行列の形で与えられる

res = Counter(chain.from_iterable(d))

for i in range(1,V):
    print(res.get(i,0)//2)


### FIXED CODE ###

N, X, Y = map(int, input().split())

X -= 1
Y -= 1
dist = [0]*(N-1)
for i in range(N):
    for j in range(i+1, N):
        dist[min(j-i, abs(X-i) + 1 + abs(Y-j))-1] += 1

print(*dist, sep="\n")
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()
### BUGGY CODE ###

N=int(input())
while True:
    try:
        listA=list(map(int,input().split()))
        #listA<-[1,2,2,3,1]
        #ここに逐次処理を書けばいいと思う。
    except:
        break;

product=1
for i in listA:
  	product=product*i
    
if product<10**18+1:
  print(product)
  
elif product>=10**18+1:
  print(-1)


### FIXED CODE ###

N=int(input())
while True:
    try:
        listA=list(map(int,input().split()))
        #listA<-[1,2,2,3,1]
        #ここに逐次処理を書けばいいと思う。
    except:
        break;

product=1
for i in listA:
  if product<10**18+1:
  	product=product*i
    
if listA.count(0)>0:
  print(0)
    
elif product<10**18+1:
  print(product)
  
elif product>=10**18+1:
  print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from fractions import Fraction
def main():
    N,K = map(int,input().split())
    countlist = []
    answer = 0
    print(N,K)
    for i in range(N):
        count = 0
        while i <= K-1:
            i += i*2
            count +=1
        countlist.append(count)
    print(countlist)
    for j in countlist:
        answer += Fraction(1,N) * Fraction(1,2)**j
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N,K = map(int,input().split())
    ans = 0
    for i in range(1,N+1):
        tmp = i
        n = 0
        while tmp < K:tmp*=2;n+=1
        ans += ((1/N)*(1/2)**n)
    print(ans)

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

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

s_list = list(s)

sum_list = []
for i in range(n):
    sum_list.append(s_list[:i].count('W') + s_list[i+1:].count('E'))

print(min(sum_list))

### FIXED CODE ###

'''
制約
2 ≤ N ≤ 3×10^5(300,000)

入力例 3
8
WWWWWEEE

出力例 3
3

考え方：
Eを0, Wを1と置くと、
0000000X11111111 と並ぶようにすればよい。
そのために、値を変える数が最小になるリーダーの位置を調べればよい

-> 左端のW(West), 右端のE(East)はほぼ必ず向きを変える必要がある。


A. 全パターン試す
ある地点より左のWの数 + 右のEの数　の合計が最小になるパターンを求める（文字一致でカウント）
-> TLE

B. 全パターン
str.count('W')でやる
-> TLE

C. 「累積和」(cumulative sum)というアルゴリズムを使わないと解けない問題。学習して、使う！


'''

# from collections import deque # キュー、スタックに利用

# sys.stdin.readline() # 標準入力の高速化に利用
import sys
input = sys.stdin.readline

is_debug = False


def main():
    '''メイン処理'''
    n = int(input())
    sss = input()

    s_list = list(sss)

    W_sums = [0] * n # 累積和を入れるリスト
    E_sums = [0] * n # 累積和を入れるリスト
    W_sum = 0 # 左端から数えて、向きを変える必要のあるWの数
    E_sum = 0 # 右端から数えて、向きを変える必要のあるWの数
    
    if is_debug:
        print(W_sums)
    
    for i in range(n):
        if s_list[i] == 'W':
            W_sum += 1
        W_sums[i] = W_sum
        if s_list[n-i] == 'E':
            E_sum += 1
        E_sums[(n-1)-i] = E_sum

    if is_debug:
        print(W_sums)
        print(E_sums)
    
    # W_sums, E_sumsを用いて、向きを変える人数が最小となる値を見つける
    min_cost = float('inf')
    for i in range(n):
        # Wを振り向かせる人数
        if i == 0:
            W_cost = 0
        else:
            W_cost = W_sums[i-1]
        # Eを振り向かせる人数
        if i == n-1:
            E_cost = 0
        else:
            E_cost = E_sums[(i-1)+1]

        if is_debug:
            print(i, W_cost, E_cost)

        cost = W_cost+E_cost
        if cost < min_cost:
            min_cost = cost
    
    print(min_cost)

if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()
### BUGGY CODE ###

S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
for j in range(1,N+1):
    s = int(S[N-j:N])
    exist[s%2019] += 1
for e in exist[1:]:
    if e > 1:
        count += e-1
count += exist[0]
print(count)


### FIXED CODE ###

S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
sum = 0
for i, s in enumerate(reversed(S)):
    sum += (int(s) * pow(10, i, 2019)) % 2019
    exist[sum % 2019] += 1
for e in exist:
    if e > 1:
        count += e*(e-1)//2
count += exist[0]
print(count)