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

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(a[1]-a[0])
for i in range(2,n):
    mi=float("inf")
    temp=1
    for j in range(i-1,-1,-1):
        if temp>k:
            break
        else:
            temp+=1
        if abs(a[i]-a[j])+dp[j]<mi:
            mi=abs(a[i]-a[j])+dp[j]
    dp[i]=mi
print(dp[n-1])

### FIXED CODE ###

import numba as nb
@nb.njit
def solve(n,k,a):
    dp=[0]*n
    dp[1]=abs(a[1]-a[0])
    for i in range(2,n):
        mi=10**9
        temp=1
        for j in range(i-1,-1,-1):
            if temp>k:
                break
            else:
                temp+=1
            if abs(a[i]-a[j])+dp[j]<mi:
                mi=abs(a[i]-a[j])+dp[j]
        dp[i]=mi
    print(dp[n-1])
n,k=map(int,input().split())
a=list(map(int,input().split()))
solve(n,k,a)
### BUGGY CODE ###

n = int(input())
s = list(input())
turn = 100

for i in range(n):
    a = s[:i]
    b = s[i+1:]
    if turn > a.count("W")+b.count("E"):
        turn = a.count("W")+b.count("E")
print(turn)

### FIXED CODE ###

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

ruisekiwa = [0]
ans = n

for i in s:
    if i == "W":
        ruisekiwa.append(ruisekiwa[-1]+1)
    else:
        ruisekiwa.append(ruisekiwa[-1])
        
for i in range(1,n+1):
    w = ruisekiwa[i-1]
    e = n-i-(ruisekiwa[-1]-ruisekiwa[i])
    ans = min(ans,w+e)
    
print(ans)
### BUGGY CODE ###

class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ships.append(Ship(f, t))

# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0
# 探索予定島
search_list = [0]

# 新たな島に移動できたなら次も探索する
while len(search_list):
  now_island = search_list.pop(0)
  # 各到達可能な島ごとに移動シミュレーション
  if reachable_islands[now_island] == float('inf'):
      continue
  # 全ての船についてシミュレート
  for ship in ships:
    # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
    if now_island == ship.land_from \
       and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
      # 到達済の印をつける
      reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
      # 到着島を探索予定リストに追加
      search_list.append(ship.land_to)

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] <= 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')


### FIXED CODE ###

class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

mid_from = set()
mid_to = set()

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ship = Ship(f, t)
  if ship.land_from == 0:
    mid_from.add(ship.land_to)
  if ship.land_to == N - 1:
    mid_to.add(ship.land_from)

# 最後の島が到達可能であるかを判定
if mid_from & mid_to:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n=int(input())
    l=[Counter(input())for i in range(n)]
    ans=0
    for i in range(len(l)):
        for j in range(len(l)):
            if i==j:
                continue
            else:
                if l[i]==l[j]:
                    ans+=1
    print(ans//2)
                    
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

from math import factorial
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


def main():
    n=int(input())
    l=[cmb(i,2) for i in Counter(["".join(sorted(input()))for i in range(n)]).values() if i>1]
    print(sum(l))
                    
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

ans = 0
maxi = n // 2
for i in range(maxi, 0, -1):
    dic = {}
    for j in range(n-i+1):
        if s[j:j+i] in dic:
            if dic[s[j:j+i]] < j:
                print(i)
                exit()
        dic[s[j:j+i]] = j+i-1
print(ans)

### FIXED CODE ###

def z_algorithm(s):
    n = len(s)
    z = [0 for i in range(n)]
    z[0] = n
    i, j = 1, 0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

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

ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())
    C=[0]*3
    for a in map(int,input().split()):
        C[a-1]+=1

    @lru_cache(None)
    def dfs(x,y,z)->float:
        if((x,y,z)==(0,0,0)): return 0.0
        if(x<0 or y<0 or z<0): return 0.0
        s=x+y+z
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/s

    print(dfs(*C))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    counter = [0] * 3
    for a in map(int, input().split()):
        counter[a - 1] += 1

    # (i, j, k) -> (i - 1, j, k), (i + 1, j - 1, k), (i, j + 1, k - 1)
    # s = i + j + k の小さい方から遷移
    dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 0
    for s in range(1, n + 1):
        for k in range(n + 1):
            for j in range(n + 1):
                i = s - j - k
                if i < 0:
                    break
                res = n
                if i: res += i * dp[i - 1][j][k]
                if j: res += j * dp[i + 1][j - 1][k]
                if k: res += k * dp[i][j + 1][k - 1]

                res /= s
                dp[i][j][k] = res

    i, j, k = counter
    print(dp[i][j][k])
resolve()
### BUGGY CODE ###

import sys
mod = int(1e9+7)
input=sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
#S[0]は使わない
S = [[0]*60 for _ in range(N)]

tmp = A[-1]
idx = 0
while tmp > 0:
    if tmp%2:
        S[-1][idx] += 1
    idx += 1
    tmp //= 2


for i in range(N-2, 0, -1):
    for j in range(60):
        S[i][j] = S[i+1][j]
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            S[i][idx] += 1
        idx += 1
        tmp //= 2

ans = 0
for i in range(N-1):
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            ans += ((N-1-i)-S[i+1][idx])*pow(2, idx, mod)%mod

        else:
            ans += S[i+1][idx]*pow(2, idx, mod)%mod

        idx += 1
        tmp //= 2
        ans %= mod
    for x in S[i+1][idx:]:
        ans += x*pow(2, idx, mod)%mod
        idx += 1
        ans %= mod

print(ans)


### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
S = [str(input()) for _ in range(n)]
count = 0
for i in range(n):
    for j in range(n):
        if i<j:
            ana1 = list(S[i])
            ana2 = list(S[j])
            ana1.sort()
            ana2.sort()
            if ana1 == ana2:
                count += 1
            
print(count)

### FIXED CODE ###

import collections

# nC2を足す理由は、同一文字列からアナグラムとなっている2つの文字列を見つけないといけないから
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
# ソートした時にそれぞれの文字がリストに分割されるからjoinで文字列に直す
c = collections.Counter(s)
ans = 0
for i in set(s):
    n = c[i]
    ans += n * (n - 1) // 2
print(ans)

# set(s)によって、同じ文字列は消去される。そしてcによって、何回その文字が出ているかを数えれる。
### BUGGY CODE ###

n,m=map(int,input().split())
alis=[]
for i in range(m):
	a=int(input())
	alis.append(a)
if 1 in alis:
	dp=[1,0]
else:
	dp=[1,1]
for i in range(2,n+1):
	if i in alis:
		d=0
		dp.append(d)
	else:
		d=dp[i-2]+dp[i-1]
		dp.append(d)
print(dp[n]%(10**9+7))


### FIXED CODE ###

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

import math
from functools import reduce

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

k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(a,b,c)

print(ans)

### FIXED CODE ###

from math import gcd
#from functools import reduce

k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(gcd(b,c),a)

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

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

def f(i):
    return sum(A[(i + j) % len(A)] * (1 if j % 2 == 0 else -1) for j in range(len(A)))

B = [f(i) for i in range(len(A))]

print(' '.join(map(str, B)))

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[0] // 2

# 2 * A[0] = B[0] + B[1]
# 2 * A[1] = B[1] + B[2]
# 2 * A[2] = B[2] + B[0]

# 2 * A[2] - 2 * A[1] = B[0] - B[1]
# 2 * A[0] - 2 * A[2] = B[1] - B[2]
# 2 * A[1] - 2 * A[0] = B[0] - B[2]

# A[0] - A[2] + A[1] = B[1]

# B[i] = A[i] + A[i - 1] - A[i + 1]

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = B[0] - B[2]
# A[1] - A[2] = B[1] - B[3]
# A[2] - A[3] = B[2] - B[4]
# A[3] - A[4] = B[3] - B[0]
# A[4] - A[0] - B[4] - B[1]

# A[0] - A[1] + A[2] - A[3] + A[4] = 2 * B[0]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)


### FIXED CODE ###

def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)
### BUGGY CODE ###

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
t = 1
sum_list = []
for i in range(a):
    for t in range(a):
        if i >= t:
            continue
        w = p[i]*p[t]
        sum_list.append(w)

print(sum(sum_list)%mod)

### FIXED CODE ###

import itertools as itr

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
ans =0
sum_list = list(itr.accumulate(p))
for i in range(len(p)-1):
    o = p[i+1]
    w =sum_list[i]
    ans = (ans+o*w%mod)%mod
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
x = [int(i) for i in input().split()]

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


def gcd_multi(n,x):
    if n==1:
        return x[0]
    else:
        element = gcd(x[0], x[1])
        if n==2:
            return element
        else:
            for i in range(2,n):
                element=gcd(element,x[i])
            return element

ans = []
for i in range(n):
    l = copy.deepcopy(x)
    del l[i]
    ans.append(gcd_multi(n-1,l))

print(max(ans))


### FIXED CODE ###

import copy
n = int(input())
x = [int(i) for i in input().split()]

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


def gcd_multi(n,x):
    if n==1:
        return x[0]
    else:
        element = gcd(x[0], x[1])
        if n==2:
            return element
        else:
            for i in range(2,n):
                element=gcd(element,x[i])
            return element

X=[0 for i in range(n)]
Y=[0 for i in range(n)]

for i in range(1,n):
    X[i]=gcd(X[i-1],x[i-1])

for i in range(n-1)[::-1]:
    Y[i]=gcd(Y[i+1],x[i+1])

Z=[gcd(X[i],Y[i]) for i in range(n)]
print(max(Z))
### BUGGY CODE ###

n=int(input())
s=input()
#000~999からいくつ作れるか試す
num='0123456789'
ans=0
#候補の暗証番号を生成する
for first_num in num:
    for second_num in num:
        for third_num in num:
            temp_lock=first_num+second_num+third_num
            temp_cnt=0
            for i in s:
                if temp_cnt==0 and i==temp_lock[0]:
                    temp_cnt=1
                elif temp_cnt==1 and i==temp_lock[1]:
                    temp_cnt=2
                elif temp_cnt==2 and i==temp_lock[2]:
                    ans+=1
                    break
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
#000~999からいくつ作れるか試す
num='0123456789'
ans=0
#候補の暗証番号を生成する
for first_num in num:
    for second_num in num:
        for third_num in num:
            temp_lock=first_num+second_num+third_num
            temp_cnt=0
            for i in s:
                if temp_cnt==0 and i==temp_lock[0]:
                    temp_cnt=1
                elif temp_cnt==1 and i==temp_lock[1]:
                    temp_cnt=2
                elif temp_cnt==2 and i==temp_lock[2]:
                    ans+=1
                    break
print(ans)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
def f(x):
    return sum(range(1, x + 1)) / x
p = [f(int(i)) for i in input().split()]
s = np.cumsum(p)
if k == 1:
    print(max(p))
elif k == n:
    print(s[-1])
else:
    print(max(s[k - 1:] - np.hstack([[0], s[:n - k]])))

### FIXED CODE ###

import sys
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
total = [0] * n
total[0] = sum(range(1, p[0] + 1)) / p[0]
max_value = 0
if k == 1:
    print(sum(range(1, max(p) + 1)) / max(p))
    sys.exit()
elif k == n:
    print(sum([sum(range(1, i + 1)) / i for i in p]))
    sys.exit()
for i in range(1, n):
    total[i] = total[i - 1] + sum(range(1, p[i] + 1)) / p[i]
    
    if i == k - 1:
        max_value = total[i]
    elif i >= k:
        max_value = max(max_value, total[i] - total[i - k])
print(max_value)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    c = int(input())
    if c not in A:
        A.append(c)
    else:
        A.remove(c)

print(len(A))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
cnt = 1
ans = 0
A.sort()
for i in range(N-1):
    if A[i] == A[i+1]:
        cnt += 1
    else:
        if cnt%2 == 1:
            ans += 1
        cnt = 1
if cnt%2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
q = int(input())
b = []
c = []
# diff = []
for i in range(q):
    _ = list(map(int, input().split()))
    c.append(_[1])
    b.append(_[0])

for i in range(q):
    for j in range(n):
        if b[i] == a[j]:
            a[j] = c[i]
    print(sum(a))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    _ = list(map(int, input().split()))
    c.append(_[1])
    b.append(_[0])

s = sum(a)

# 辞書型で度数を持つ
hist = {}
for i in range(n):
    if a[i] in hist:
        hist[a[i]] += 1
    else:
        hist[a[i]] = 1
# print(hist)

for i in range(q):
    diff = c[i] - b[i]
    if b[i] in hist:
        s += hist[b[i]]*diff
        print(s)
        if c[i] in hist:
            hist[c[i]] += hist[b[i]]
            del hist[b[i]]
        else:
            hist[c[i]] = hist[b[i]]
            del hist[b[i]]
    else:
        print(s)
    # print(hist)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
# 連続するK要素を選ぶパターン、n-k+1
mink=min(p[:k])
maxk=max(p[:k])
eq=list(range(n-k+1))
for i in range(n-k+1-1):
  if p[i]==mink and p[i+k]>maxk:
    eq[i+1]=eq[i]
    pass
  if p[i]==mink:
    mink=min(p[i+1:i+k+1])
    maxk=max(maxk,p[i+k])
  if p[i]==maxk:
    mink=min(mink,p[i+k])
    maxk=max(p[i+1:i+k+1])
  else:
    mink=min(mink,p[i+k])
    maxk=max(maxk,p[i+k])
s=-1
for i in range(n-k+1):
  a=p[i]
  f=True
  for b in p[i+1:i+k]:
    if a<b:
      a=b
      continue
    else:
      f=False
      break
  if f:
    if s==-1:
      s=i
    else:
      eq[i]=s

print(len(set(eq)))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))

#スライド最小値、スライド最大値
from collections import deque
def slide_max_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    max_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] < a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        max_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return max_idx
def slide_min_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    min_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] > a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        min_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return min_idx

min_idx=slide_min_index(p,k+1)
max_idx=slide_max_index(p,k+1)
eq=list(range(n-k+1))
for i in range(n-(k+1)+1):
  if i==min_idx[i+k] and i+k==max_idx[i+k]:
    eq[i+1]=eq[i]

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))
#print(eq)
#print(a)
### BUGGY CODE ###

import numpy as np
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

ex = [[1,2], [0,2], [0,1]]
dp = np.array([abc[0]] + [[0]*3 for _ in range(n-1)])

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + np.max(np.take(dp[i], ex[j]))

print(max(dp[-1]))

### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[0,0,0] for _ in range(n)]

dp[0] = abc[0]
ls = [[1,2], [0,2], [0,1]]

if n == 1:
    ans = min(dp[0])
else:
    for i in range(1,n):
        for j in range(3):
            dp[i][j] = max([ dp[i-1][k] for k in ls[j] ]) + abc[i][j]

print(max(dp[-1]))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

def b_search(L,key,left,right):
    #L[i] < keyを満たす最大のi
    #L[i] < key <= L[i+1]
    if key <= L[left]:
        return 0
    elif key > L[len(L)-1]:
        return len(L)
    else:
        mid = (left+right)//2
        if L[mid] < key and key <= L[mid+1]:
            return mid + 1
        elif L[mid] >= key:
            return b_search(L,key,left,mid)
        else:
            return b_search(L,key,mid,right)

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += b_search(L,L[i]+L[j],0,len(L))-(j+1)
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

Rs = []
Gs = []
Bs = []
for i, il in enumerate(S):
    if il == 'R':
        Rs.append(i)
    if il == 'G':
        Gs.append(i)
    if il == 'B':
        Bs.append(i)
num = 0
for i in range(N):
    for step in range(1, N):
        j = i + step
        k = i + 2*step
        if k > N - 1:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            num += 1
print(len(Rs)*len(Gs)*len(Bs) - num)


### FIXED CODE ###

N = int(input())
S = input()

Rs = 0
Gs = 0
Bs = 0
for il in S:
    if il == 'R':
        Rs += 1
    if il == 'G':
        Gs += 1
    if il == 'B':
        Bs += 1
num = 0
for i in range(N):
    for step in range(1, N):
        j = i + step
        k = i + 2*step
        if k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            num += 1
print(Rs*Gs*Bs - num)
### BUGGY CODE ###

import itertools
n = int(input())
s = input()
l = set(list(itertools.combinations(s,3)))
print(len(l))


### FIXED CODE ###

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

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    if (ss[0] in s):
        ind1 = s.index(ss[0])
        if (ss[1] in s[ind1+1:]):
            ind2 = ind1+1 + s[ind1+1:].index(ss[1])
            if (ss[2] in s[ind2+1:]):
                ans += 1

print(ans)