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

ans=0
n=int(input())
k=str(input())
r=k.count("R")
b=k.count("B")
g=k.count("G")
ans+=r*b*g
    
for i in range(n-2):
  ii=k[i]
  for j in range(i+1,n-1):
    jj=k[j]
    l=j+(j-i)
    #print(l)
    if jj!=ii and l<n:
      #print(i,j)
      ll=k[l]
      if ii!=ll and jj!=ll:
        ans-=1
          #print(i,j,l)
print(ans)

### FIXED CODE ###

ans=0
n=int(input())
k=str(input())
r=k.count("R")
b=k.count("B")
g=k.count("G")
ans+=r*b*g
    
for i in range(n-2):
  ii=k[i]
  for j in range(i+1,(n-i)//2+1+i):
    jj=k[j]
    l=j+(j-i)
    #print(l)
    if jj!=ii and l<n:
      #print(i,j)
      ll=k[l]
      if ii!=ll and jj!=ll:
        ans-=1
          #print(i,j,l)
print(ans)
### BUGGY CODE ###

n,W = map(int,input().split())
vw=[list(map(int,input().split())) for i in range(n)]
v=[vw[i][1] for i in range(n)]
w=[vw[i][0] for i in range(n)]
dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])

### FIXED CODE ###

n,W = map(int,input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])
### BUGGY CODE ###

def main():
  n = int(input())
  a = list(map(int,input().split()))
  q = int(input())
  for _ in range(q):
    b, c = map(int, input().split())
    for i in range(0,n):
      if(a[i]==b):
        a[i]=c
    print(sum(a))
main()

### FIXED CODE ###

import collections
def main():
  n = int(input())
  a = list(map(int,input().split()))
  ans=sum(a)
  counter = collections.Counter(a)
  q = int(input())
  for _ in range(q):
    b, c = map(int, input().split())
    num=counter[b]
    counter[b]=0
    counter[c]+=num
    ans+=(c-b)*num
    print(ans)
main()
### BUGGY CODE ###

N = int(raw_input())

pw = 1

for i in range(1,N+1):
    pw = pw * i

print pw % (10**9 + 7)


### FIXED CODE ###

N = int(raw_input())

v = 10**9 + 7

t = 1
mod = []
for i in range(1,N+1):
    t = t * i
    if (t > v):
        mod.append(t % v)
        t = 1 #reset
mod.append(t % v)

#print mod

s = 1
for j in range(len(mod)):
    s = s * mod[j]

ans = s % v
print ans
### BUGGY CODE ###

import sys
from itertools import permutations as perm
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def solve():
    def get_ans(c1, c2, c3):
        ret = 0
        lenc3 = len(RGB[c3])
        for c1i in range(len(RGB[c1])):
            tmp = bisect(RGB[c2], RGB[c1][c1i])
            for c2i in range(tmp, len(RGB[c2])):
                c3i = bisect(RGB[c3], RGB[c2][c2i])
                if lenc3 == c3i:
                    continue
                # print(c1i, c2i, c3i)
                c21d = RGB[c2][c2i] - RGB[c1][c1i]
                t = bisect(RGB[c3], RGB[c2][c2i] + c21d, c3i)

                if lenc3 != t and RGB[c3][t] - RGB[c2][c2i] == c21d:
                    ret += lenc3 - c3i - 1
                else:
                    ret += lenc3 - c3i

        return ret
    int(input())
    S = list(input().strip())
    RGB = {k: [] for k in "RGB"}
    for i, s in enumerate(S):
        RGB[s].append(i)

    ans = 0
    # print(RGB)
    for c1, c2, c3 in perm(list("RGB")):
        # print(c1, c2, c3)
        ans += get_ans(c1, c2, c3)
        # print(ans)
    print(ans)


solve()


### FIXED CODE ###

import sys
from itertools import permutations as perm
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def solve():
    def get_ans(c1, c2, c3):
        ret = 0
        lenc3 = len(RGB[c3])
        for c1i in range(len(RGB[c1])):
            tmp = bisect(RGB[c2], RGB[c1][c1i])
            for c2i in range(tmp, len(RGB[c2])):
                c3i = bisect(RGB[c3], RGB[c2][c2i])
                if lenc3 == c3i:
                    continue
                # print(c1i, c2i, c3i)
                c21d = RGB[c2][c2i] - RGB[c1][c1i]
                t = bisect(RGB[c3], RGB[c2][c2i] + c21d, c3i)

                if lenc3 != t and RGB[c3][t] - RGB[c2][c2i] == c21d:
                    ret += lenc3 - c3i - 1
                else:
                    ret += lenc3 - c3i

        return ret
    int(input())
    S = list(input().strip())
    RGB = {k: [] for k in "RGB"}
    for i, s in enumerate(S):
        RGB[s].append(i)

    ans = 0
    # print(RGB)
    for c1, c2, c3 in perm(list("RGB")):
        # print(c1, c2, c3)
        ans += get_ans(c1, c2, c3)
        # print(ans)
    print(ans)


solve()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    for i in range(60):
        cnt = 0
        for a in A:
            cnt += (a >> i) & 1
        res += (cnt * (n - cnt) % mod) * (1 << i) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import numpy as np
MOD = 10 ** 9 + 7

n = int(input())
a = np.array(list(map(int, input().split())))
l = len(bin(max(a))) - 2

ans = 0
for i in range(l):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    now = x * (n - x) * pow(2, i, MOD) % MOD
    ans += now

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

n,m=map(int,input().split())
ls=[int(input()) for i in range(m)]

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    while True:
        row=[]
        previous=dp_table[-1]
        for i in range(n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)

print(dp(n,ls)%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[-1]%mod)
### BUGGY CODE ###

def gcd(a,b,c):
  bound=min([a,b,c])
  for d in range(bound,0,-1):
    if a%d==b%d==c%d==0:
      return d
def main():
  k=int(input())
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=gcd(a,b,c)
        
  return cur
print(main())

### FIXED CODE ###

import math
  
def main():
  k=int(input())
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=math.gcd(math.gcd(a,b),c)
        
  return cur
print(main())
### BUGGY CODE ###

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(len(uf.members(i)) - len(block_list[i]))
print(*ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(uf.size(i) - len(block_list[i]))
print(*ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce


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


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def g(x, y):
    return (cmb(x + y + 2, y + 1) - 1) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)


### FIXED CODE ###

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


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return (over[n] * under[r] * under[n - r]) % MOD


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    # print(r, w)
    while w[2] != 1:
        # print(r, w)
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


def mod_inv(a, m):
    _, x = extGCD(m, a)
    return (x + m) % m


def g(x, y):
    return (cmb(x + y + 2, x + 1) - 1 + MOD) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

over = [0 for i in range(r2 + c2 + 3)]
under = [0 for i in range(r2 + c2 + 3)]
over[0] = 1
for i in range(r2 + c2 + 2):
    over[i + 1] = over[i] * (i + 1) % MOD

under[r2 + c2 + 2] = mod_inv(over[r2 + c2 + 2], MOD)
for i in range(r2 + c2 + 1, 0, -1):
    under[i] = under[i + 1] * (i + 1) % MOD

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)
### BUGGY CODE ###

import sys
import numpy as np
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def combinations_count(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))


N = INT()
A = LIST()

ans = 0

C = Counter(A)
for i in list(C.values()):
    ans += combinations_count(i, 2)

for i in range(N):
    tmp = ans - combinations_count(C[A[i]], 2) + combinations_count(C[A[i]] - 1, 2)
    print(tmp)


### FIXED CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A_c = Counter(A)

A_c_c = 0
for i in A_c.values():
    A_c_c += i*(i-1)//2

for k in range(N):
    ans = A_c_c - (A_c[A[k]] - 1)
    print(ans)
### BUGGY CODE ###

import math
n = int(input())
mylist = [int(math.sqrt(i)) for i in range(1,n+1)]

def main():
    for N in range(1,n+1):
        result = 0
        for x in range(1,mylist[N-1]+1):
            tempx = x**2
            for y in range(x, mylist[N-x**2]+1):
                tempy = y**2
                tempxy = x*y
                if N-tempx-tempy-tempxy < 0:
                    break
                else:
                    for z in range(y, mylist[N-tempx-tempy-tempxy]+1):
                        if tempx + tempy + z**2 + tempxy + y*z + z*x == N:
                            if x != y and y != z:
                                result += 6
                            elif x == y and y == z:
                                result += 1
                            else:
                                result += 3
                        elif tempx + tempy + z**2 + tempxy + y*z + z*x > N:
                            break
        print(result)
main()

### FIXED CODE ###

import math
n = int(input())
mylist = [int(math.sqrt(i)) for i in range(1,n+1)]
mylist = [0]+mylist

def main():
    for N in range(1,n+1):
        result = 0
        for x in range(1,mylist[N//3]+1):
            tempx = x**2
            for y in range(x, mylist[(N-x**2)//2]+1):
                tempy = y**2
                tempxy = x*y
                tempxandy = (x+y)/2
                tempnum = N-tempx-tempy-tempxy+tempxandy**2
                if tempnum <= 0:
                    break
                else:
                    if math.sqrt(tempnum)*2 == int(math.sqrt(tempnum)*2):
                        z = math.sqrt(tempnum)-tempxandy
                        #print(x,y,z,N)
                        if z < y:
                            break
                        elif x != y and y != z:
                            result += 6
                        elif x == y and y == z:
                            result += 1
                        else:
                            result += 3
        print(result)
main()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
#S  = input()
#s = []
s = [0 for i in range(Q)]
#print(s)
for i in range(Q):
    l,r = map(int,input().split())
    #s.append(0)
    j = l-1
    while j < r-1:
    #for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            s[i] += 1
            j += 1
        j += 1
for i in range(Q):
    print(s[i])
#for i in range(Q):
#    print(S[i].count("AC"))


### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
a =[0] * N
for i in range(N-1):
    if S[i] == "A" and S[i + 1] == "C":
        a[i + 1] = a[i] + 1
    else:
        a[i + 1] = a[i]
l, r = 0, 0
b = [0] * Q
for i in range(Q):
    l, r = map(int, input().split())
    b[i] = a[r-1] - a[l-1]
for i in range(Q):
    print(b[i])
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under%mod
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print(ans%mod)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
A=n*m-2
from math import factorial
def Comb(N, K):
    a = factorial(N) % mod
    b = factorial(K) % mod
    c = factorial(N-K) % mod
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
v=Comb(A,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print(ans%mod)
### BUGGY CODE ###

N = int(input())

print(0, flush=True)
begin = input()

l, r = 0, N
while abs(r - l) > 1:
    mid = (l+r) // 2
    print(mid, flush=True)
    sol = input()
    if sol == "Vacant":
        l = mid
        break
    elif sol % 2 == 0:
        if sol != begin:
            r = mid
        else:
            l = mid
    else:
        if sol != begin:
            l = mid
        else:
            r = mid

print(l)


### FIXED CODE ###

N = int(input())

print(0, flush=True)
begin = input()

l, r = 0, N
while abs(r - l) > 1:
    mid = (l+r) // 2
    print(mid, flush=True)
    sol = input()
    if sol == "Vacant":
        l = mid
        break
    elif mid % 2 == 0:
        if sol != begin:
            r = mid
        else:
            l = mid
    else:
        if sol != begin:
            l = mid
        else:
            r = mid

print(l)
### BUGGY CODE ###

N = int(input())
# C:移動時間 S:start時間 F:運行間隔 SはFで割り切れる
CSF = [list(map(int, input().split())) for i in range(N-1)]

for i in range(N-1):
    time = 0
    time += CSF[i][1]
    for j in range(i, N-1):
        start = CSF[j][1]
        while True:
            if time <= start:
                break
            else:
                start += CSF[j][2]
        time += (start - time)
        time = max(time, CSF[j][1])
        time += CSF[j][0]

    print(time)

print(0)





### FIXED CODE ###

N = int(input())
CSF = [list(map(int, input().split())) for i in range(N-1)]

# 鉄道種類ループ
for i in range(N):
    T = 0
    # 鉄道乗り継ぎループ
    for j in range(i, N-1):
        if T < CSF[j][1]:
            T = CSF[j][1]
        else:
            if T % CSF[j][2] != 0:
                T += (CSF[j][2] - T % CSF[j][2])
        T += CSF[j][0]
    print(T)
### BUGGY CODE ###

import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
sm=0
for i in C:
  b=bisect.bisect_left(B,i)
  for j in B[:b]:
    sm+=bisect.bisect_left(A,j)
print(sm)
  

### FIXED CODE ###

import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
sm=0
for j in B:
  sm+=bisect.bisect_left(A,j)*(n-bisect.bisect_right(C,j))
print(sm)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = []
for _ in range(M):
    B, C = map(int, input().split())
    B_C.append((C, B))
B_C = sorted(B_C, reverse=True)
Cs = []
rem = N
for c, b in B_C:
    if rem >= b:
        Cs += [c]*b
    else:
        Cs += [c]*rem
        break
ans = sum(sorted(A+Cs, reverse=True)[:N])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = []
for _ in range(M):
    B, C = map(int, input().split())
    B_C.append((C, B))
B_C = sorted(B_C, reverse=True)
Cs = []
rem = N
for c, b in B_C:
    if rem >= b:
        Cs += [c]*b
        rem -= b
    else:
        Cs += [c]*rem
        break
ans = sum(sorted(A+Cs, reverse=True)[:N])
print(ans)
### BUGGY CODE ###

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

def leng(n, f):
    return math.ceil(n / f) - 1

logs = np.array(A)
vleng = np.vectorize(leng)

#めぐる式二分探索
def is_ok(i):
    if sum(vleng(logs, i)) <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, 10 ** 9 + 1))

### FIXED CODE ###

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

#めぐる式二分探索
def is_ok(i):
    su = 0
    for a in A:
        su += (a-1) // i
    if su <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A) + 1))
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        if i > 0 and a[i] == a[i-1]:
            continue
        if i + 1 < n and a[i] == a[i+1]:
            continue
        isDiv = False
        for j in range(i):
            if i != j and a[i] % a[j] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
import collections
sys.setrecursionlimit(10**6)

M = 10**6+5


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * M
    for i in range(n):
        if cnt[a[i]] != 0:
            cnt[a[i]] += 1
            continue

        for j in range(a[i], M, a[i]):
            cnt[j] += 1
    ans = 0
    for i in range(n):
        if cnt[a[i]] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

from collections import Counter

S = input()
N = len(S)

s = [0 for _ in range(N)]

num = ""
for i in range(N-1, -1, -1):
    num = S[i] + num
    s[i] += int(num)%2019

ans = 0
# print(Counter(a))
for key, val in Counter(s).items():
    if key == 0:
        ans += val
    if val >= 2:
        ans += val*(val-1)//2
print(ans)

### FIXED CODE ###

S = input()
N = len(S)

num = [0] * 2019
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    ans += num[now]
    num[now] += 1
print(ans)