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

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

a=[0]*(N+1)
r=[0]*P

if P!=2 and P!=5:
    for i in range(N):
        a[i] = int(S[i:])
    for i in range(N+1):
        temp=a[i]%P
        r[temp]+=1
    ans=0
    for i in range(P):
        ans+=r[i]*(r[i]-1)//2
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)



### FIXED CODE ###

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

a = [0] * (N + 1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = ((int(S[N-i])*tenfactor+a[i-1])%P)
        tenfactor*=10
        tenfactor%=P

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

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

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort()
b.sort()
c.sort()

def binary_search(x,i):
	low = 0
	high = len(x)-1
	t = (low + high) // 2 	
	while (low<=high):
		if (i==x[t]):
			break
		elif (i > x[t]):
			low = t + 1
		elif (i < x[t]):
			high = t - 1
		t = (low + high) // 2
	return t

ans=0
for i in range(n):
  b_l=binary_search(b,a[i])
  for j in range(b_l+1,n):
    c_l=binary_search(c,b[j])
    ans+=n-c_l-1

print(ans)   

### FIXED CODE ###

import bisect

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
	a_l=bisect.bisect_left(a,b[i])
	c_l=bisect.bisect(c,b[i])
	ans+=a_l*(n-c_l)

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

n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)]for j in range(n)]
#pre
for i in range(n):
    k = bin(a[i])
    k = k[::-1]
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = bin(a[i])
    k = list(map(int, k[:1:-1]))
    k = k + [0 for i in range(leng - len(k))]
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
import numpy as np

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i, j))

for i in slist:
    s = bfs(i[0], i[1])

print(s)


### FIXED CODE ###

from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
si=[{i} for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    si[rx]=si[ry]|si[rx]
    sp[rx]=sp[rx]|sp[ry]
  else:
    r[ry]=rx
    si[rx]=si[rx]|si[ry]
    sp[rx]=sp[rx]|sp[ry]
    if r[rx]==r[ry]:
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc051/tasks/abc051_b
# -*- coding: utf-8 -*-
K,S = map(int,input().split())
ans = 0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k == S: ans +=1 
print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc051/tasks/abc051_b
# -*- coding: utf-8 -*-
K,S = map(int,input().split())
ans = 0
for i in range(0,K+1):
  for j in range(0,K+1):
    z = S-i-j
    if 0 <= z <= K: ans +=1
print(ans)
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
count=1
li2=[]
if(len(li)!=1):
    for i in range(1,n):
        li2=li[0:i]
        if(min(li2)>=li[i]):
            count+=1
print(count)


### FIXED CODE ###

n=int(input())
li = list(map(int,input().split()))
count=1
m=n
for i in range(1,n):
    m=min(m,li[i-1])
    if(m==1):
        break
    if(m>=li[i]):
        count+=1
print(count)
### BUGGY CODE ###

N = int(input())
flg = 0
for c in range(1,N):
    s = N - c 
    for a in range(1,s+1):
        if s%a == 0:
            flg+=1
            
print(flg)

### FIXED CODE ###

N = int(input())
flg = 0
for c in range(1,N):
    flg += (N-1)//c
            
print(flg)
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

n=int(input())
a=list(int(input())for _ in range(n))
b=sorted(a,reverse=True)
for i in range(n):
    if max(a)!=a[i]:
        print(max(a))
    else:
     print(b[1])

### FIXED CODE ###

n=int(input())
a=list(int(input())for _ in range(n))
b=sorted(a,reverse=True)
for i in range(n):
    if b[0]!=a[i]:
        print(b[0])
    else:
     print(b[1])
### BUGGY CODE ###

import math
X=int(input())
shukai=360
while True:
    if shukai%X==0:
        print(shukai//X)
        exit()
    else:
        shukai*=2

### FIXED CODE ###

def gcda(a,b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcda(r, b)

def lcm(a,b):
    return a*b//gcda(a,b)

X=int(input())
shukai=360
while True:
    if shukai%X==0:
        print(shukai//X)
        exit()
    else:
        shukai=lcm(shukai,X)
### BUGGY CODE ###

import re
s=input()
m=0
for i in range(len(s)):
  dst = re.sub(r'01|10', "", s)
  if dst == s:
    break
  m += len(s) - len(dst)
  s=dst
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
cnt = 0
for index, i in enumerate(A):
    #print("index:{}".format(index))
    for j in range(index + 1):
        if i > A[j]:
            #print("break:{}".format(j))
            break
        elif index == j or A[j] == 1:
            ans += 1
            break

print(ans)

### FIXED CODE ###

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


for index, i in enumerate(A):
    if index == 0:
        ans += 1
        small = i


    elif small >= i:
        ans += 1
        small = i      

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

from collections import Counter
n=int(input())
l=list(map(int,input().split()))
f=l[0::2]
s=l[1::2]
ans=[]
if len(Counter(l).values()) == 1:
  ans.append(len(f))
elif len(Counter(f).values()) == len(Counter(s).values()) == 1:
  ans.append(0)
else:
  for fk,fv in sorted(Counter(f).items(),key=lambda x:x[0]):
    fdk=fk
    a=sum(Counter(f).values())-fv
    for sk,sv in sorted(Counter(s).items(),key=lambda x:x[0]):
      if fk != sk:
        ans.append(a+sum(Counter(s).values())-sv)
print(min(ans))

### FIXED CODE ###

from collections import Counter
n=int(input())
l=list(map(int,input().split()))
f=l[0::2]
s=l[1::2]
fn=sorted(Counter(f).items(),key=lambda x:x[1],reverse=True) + [(0, 0)]
sn=sorted(Counter(s).items(),key=lambda x:x[1],reverse=True) + [(0, 0)]
if fn[0][0]!=sn[0][0]:
  ans=n-fn[0][1]-sn[0][1]
else:
  ans=n-max(fn[1][1]+sn[0][1],fn[0][1]+sn[1][1])
print(ans)
### BUGGY CODE ###

xx = []
n, k = map(int, input().split())
for i in range(n):
  a, b = map(int, input().split())
  for j in range(b):
    xx.append(a)

yy = sorted(xx)
print(yy[k-1])


### FIXED CODE ###

xx = []
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
xx = sorted(ab, key= lambda x:x[0])

ans = 0
for i in range(n):
  ans += xx[i][1]
  if ans >=  k:
    print(xx[i][0])
    break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(n - 1):
    for j in range(i,n):
        ans += a[i]^a[j]
        ans %= MOD
print(ans%MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(60):
    tmp0 = 0
    tmp1 = 0
    for j in range(n):
        if a[j]>>i&1 == 0: tmp0 += 1
        else: tmp1 += 1
    ans += (tmp0*tmp1%MOD)*(2**i%MOD)
print(ans%MOD)
### BUGGY CODE ###

MOD = 10**9 + 7

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

ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        ans += a[i] * a[j]
        ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7

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

s = sum(a)
ans = 0

for i in range(n-1):
    s -= a[i]
    ans += a[i] * s
    ans %= MOD

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

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

K = len(bin(np.max(A))) - 2

ans = 0
mod = 10 ** 9 + 7

for i in range(K):
    bit = sum(A >> i & 1)
    ans += pow(2, i, mod) * bit * (N - bit)
    ans %= mod

print(ans)

### FIXED CODE ###

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

K = len(bin(np.max(A))) - 2

ans = 0
mod = 10 ** 9 + 7
N %= mod

for i in range(K):
    bit = np.count_nonzero(A >> i & 1) % mod
    ans += 2 ** i * bit * (N - bit)
    ans %= mod
    
print(ans)
### BUGGY CODE ###

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

index = [i for i in range(N)]

dict_value = {key: val for key, val in zip(index, P)}
ac = [dict_value[i] for i in range(N) if dict_value[i] <= min([v for k, v in dict_value.items() if k <= i])]

print(len(ac))


### FIXED CODE ###

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

value = 10 ** 9
ans = 0
for v in P:
    if v < value:
        ans += 1
        value = v
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
dp = [True]*(max(A)+1)

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], max(A)+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
dp = [True]*(A[-1]+1)

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], A[-1]+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

S = [ord(s) - ord('a') for s in input().rstrip()]

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = np.zeros((2,26),dtype=np.int32)
dp[N][0] += INF

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    arr = prev.copy()
    s = S[n]
    arr[0,s] = n
    arr[1,s] = prev[1].min() + 1
    dp[n] = arr

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    x = np.argmin(dp[i][1])
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0,x]
    i += 1

print(''.join(answer))

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = [ord(s) - ord('a') for s in input().rstrip()]

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = [[INF] * 26, [0] * 26, 0]

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    cur = [prev[0].copy(), prev[1].copy(), prev[2]]
    s = S[n]
    cur[0][s] = n
    cur[1][s] = prev[2] // 26 + 1
    cur[2] = prev[2] + cur[1][s] - prev[1][s]
    dp[n] = cur

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    L = dp[i][2] // 26
    for x in range(26):
        if dp[i][1][x] == L:
            break
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0][x]
    i += 1

print(''.join(answer))
### BUGGY CODE ###

#x,y,z = list(map(int,input().split()))
# k = int(input())

import numpy as np

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for kk in range(1,k+1):
            if i == j == kk:
                ans += i
                continue
            ans += np.gcd(np.gcd(i,j),kk)            

print(ans)


### FIXED CODE ###

#x,y,z = list(map(int,input().split()))
# k = int(input())

import math
from functools import reduce

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

def gcd_list(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 kk in range(1,k+1):
            ans += gcd(i,j,kk)


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

#!/usr/bin/env python3

s = str(input())

mod = 2019

ans = 0
for i in range(1, len(s)+1):
    for j in range(0, len(s)-i+1):
        num = int(s[j:j+i])
        if num % mod == 0:
            ans += 1
            # print(j, j+i)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(len(div_memo)):
    ans += div_memo[i]*(div_memo[i]-1)//2

ans += div_memo[0]
print(int(ans))
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
T = [sorted(s) for s in S]
ans = 0
for i in range(N):
  for j in range(i+1,N):
    if T[i] == T[j]:
      ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for _ in range(N)]
T = [''.join(sorted(s)) for s in S]
countT = Counter(T)
ans = 0
for v in countT.values():
  ans += v * (v-1) //2
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    MOD = 10**9 + 7
    t = 0
    k = max(A)
    while k>0:
        k=k//2
        t+=1

    bisu = [0]*(t+1)
    zerobi = [0]*(t+1)
    res = 0
    for i in range(n):
        for j in range(t+1):
            if A[i]&(1<<j):
                bisu[j]+=1

    for i in range(t+1):
        res = res + (bisu[i]*(n-bisu[i])*(2**i))%MOD
    print(res%MOD)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    MOD = 10**9 + 7
    t = 0
    k = max(A)
    while k>0:
        k=k//2
        t+=1

    bisu = [0]*(t+1)
    zerobi = [0]*(t+1)
    res = 0
    for i in range(n):
        for j in range(t+1):
            if A[i]&(1<<j):
                bisu[j]+=1

    for i in range(t+1):
        res = res + (bisu[i]*(n-bisu[i])*(2**i))%MOD
    print(res%MOD)

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

# -*- coding: utf-8
N = 0
C = []
S = []
F = []

# i駅での到着時間を指定すると、次の乗車時間が帰ってくる
def getNextTrain(i, time):
  t = S[i]
  while(1):
    if t >= time:
      break
    t += F[i]

  return t

# 入力部分
N = int(raw_input())
for i in range(N-1):
  c, s, f = map(int, raw_input().split())
  C.append(c)
  S.append(s)
  F.append(f)

# 処理部分
for k in range(N):
  arrive = 0
  for p in range(k, N-1): 
    # p駅から出発して
    arrive = getNextTrain(p, arrive)
    #print str(arrive) + '-> ' + str(p),
    arrive += C[p]
    #print '->' + str(arrive)
  print arrive

# 出力部分

### FIXED CODE ###

# -*- coding: utf-8
N = 0
C = []
S = []
F = []

# i駅での到着時間を指定すると、次の乗車時間が帰ってくる
def getNextTrain(i, time):
  # t = S[i]
  if time <= S[i]:
    return S[i]
  else:
    n = time / F[i]
    m = time % F[i]
    t = F[i] * n
    if m != 0:
      t += F[i]
    # while(1):
    #   if t >= time:
    #     break
    #   t += F[i]

    return t

# 入力部分
N = int(raw_input())
for i in range(N-1):
  c, s, f = map(int, raw_input().split())
  C.append(c)
  S.append(s)
  F.append(f)

# 処理部分
for k in range(N):
  arrive = 0
  for p in range(k, N-1): 
    # p駅から出発して
    arrive = getNextTrain(p, arrive)
    #print str(arrive) + '-> ' + str(p),
    arrive += C[p]
    #print '->' + str(arrive)
  print arrive

# 出力部分
### BUGGY CODE ###

from collections import defaultdict
d = defaultdict(int)
N = int(input())
A = [int(i) for i in input().split()]
B = set(A)
for i in B:
  for j in A:
    if i == j:
      d[i] += 1
cnt = 0
for i, j in d.items():
  if i < j:
    cnt += j-i
  elif i > j:
    cnt += j   
print(cnt)

### FIXED CODE ###

N = int(input())
A = sorted(int(i) for i in input().split())+[0]
cnt, ans = 0, 0
a = A[0]
for i in range(len(A)):
  if a == A[i]:
    cnt += 1
  elif a != A[i]:
    if cnt < a:
      ans += cnt
    elif cnt > a:
      ans += cnt-a
    a = A[i]
    cnt = 1
print(ans)
### BUGGY CODE ###

#C問題
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))

DP = [0 for i in range(N)]
for i in range(N):
    if i == 0:
        if i+1 not in a:
            DP[0] = 1
        else:
            DP[0] = 0
    elif i == 1:
        if i+1 not in a:
            DP[1] = DP[0]+1
        else:
            DP[1] = 0
    else:
        if i+1 not in a:
            DP[i] = DP[i-1]+DP[i-2]
        else:
            DP[i] = 0
            
print(DP[N-1]%1000000007)


### FIXED CODE ###

#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = -1
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    #print(stairs)
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)
### BUGGY CODE ###

A,B=map(int, input().split()) 
S=A*B
for i in range(1,S+1):
    if i%A==0 and i%B==0:
        Min=i
        break
print(Min)

### FIXED CODE ###

A,B=map(int, input().split()) 
N=max(A,B)
M=min(A,B)
for i in range(0,M):
    if M%(M-i)==0 and N%(M-i)==0:
        Max=M-i
        break
print(A*B//Max)
### BUGGY CODE ###

import numpy as np
 
HN = list(map(int, input().split()))
H = HN[0]; N = HN[1]
AB = [list(map(int, input().split())) for _ in range(N)]
 
DP = np.zeros((N,H))
 
for i in range(H):
    DP[0][i] = int((1+i//AB[0][0])*AB[0][1])
 
for i in range(1,N):
    for j in range(H):
        if j<AB[i][0]:
            DP[i][j] = int(min([DP[i-1][j], AB[i][1]]))
        else:
            DP[i][j] = min([DP[i-1][j], DP[i][j-AB[i][0]] + AB[i][1]])
 
print(int(DP[N-1][H-1]))

### FIXED CODE ###

HN = list(map(int, input().split()))
H = HN[0]; N = HN[1]
AB = [list(map(int, input().split())) for _ in range(N)]
 
DP = [[0]*H for i in range(N)]
 
for i in range(H):
    DP[0][i] = int((1+i//AB[0][0])*AB[0][1])
 
for i in range(1,N):
    for j in range(H):
        if j<AB[i][0]:
            DP[i][j] = int(min([DP[i-1][j], AB[i][1]]))
        else:
            DP[i][j] = min([DP[i-1][j], DP[i][j-AB[i][0]] + AB[i][1]])
 
print(int(DP[N-1][H-1]))
### BUGGY CODE ###

from bisect import bisect_right
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0

A.sort()
B.sort()
C.sort()

for i in range(N):
    a = A[i]
    bb = bisect_right(B, a)
    if bb == N + 1:
        continue
    for j in range(bb, N):
        b = B[j]
        cc = bisect_right(C, b)
        if cc == N + 1:
            continue
        ans += (N - cc)
print(ans)


### FIXED CODE ###

from bisect import bisect_right, bisect_left
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for j in range(N):
    b = B[j]
    i = bisect_left(A, b)
    k = bisect_right(C, b)
    ans += i * (N - k)
print(ans)