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

if __name__ == "__main__":
    A, B, C, K = list(map(int, input().split()))
    sum = 0
    for i in range(K):
        if i < A:
            sum += 1
        elif A<= i < A+B:
            sum = sum
        elif A+B <= i < A+B+C:
            sum -= 1
    print(sum)

### FIXED CODE ###

if __name__ == "__main__":
    A, B, C, K = list(map(int, input().split()))
    if A > K:
        print(K)
    elif A <= K <= A+B:
        print(A)
    else:
        print(A-1*(K-A-B))
### BUGGY CODE ###

def main():
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      for i in range(1, n):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  l = lcm(a)
  b= [l//i%ov for i in a]
  print(sum(b)%ov)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

data = input()
l = data.split()
l = list(map(int, l))
N, M = l[0], l[1]

s = input()
prices = s.split()
prices = list(map(int, prices))

#prices.sort(reverse = True)
#print(prices)

for i in range(M): #　半額券の数だけループ
    prices.sort(reverse = True)
    prices[0] = int(prices[0] / 2)

print(sum(prices))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
values = list(map(int, input().split()))
sortedValues = []

for v in values:
    heapq.heappush(sortedValues, (-1)*v)

for i in range(M):
    heapq.heappush(sortedValues, int((heapq.heappop(sortedValues) * 1/2)))

print((-1) * sum([heapq.heappop(sortedValues) for i in range(len(sortedValues))]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    visited = [0]
    now = 0
    ind = 0
    for _ in range(K):
        a = A[now]-1
        if a in visited:
            ind = visited.index(a)
            break
        else:
            visited.append(a)
            now = a

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    # N = 2*(10**4)
    # K = 10**18
    # A = [i+2 for i in range(N)]
    # A[-1] = 1
    # print(A)

    visited = [0]
    visited_set = set([0])
    now = 0
    ind = 0
    my_append = visited.append
    my_add = visited_set.add
    for i in range(K):
        a = A[now]-1
        if a in visited_set:
            ind = visited.index(a)
            break
        else:
            my_add(a)
            my_append(a)
            now = a
            # ind = i

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


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

N = int(input())
A = input().split()
ans = 0
for l in range(N):
    ans += A.count(A[l]) - 1
ans /= 2
for k in range(N):
    print(int(ans - (A.count(A[k]) - 1)))

### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

from collections import deque, defaultdict
from time import time

N = int(input())
A = deque([(i, deque(map(lambda a: int(a) - 1, input().split()))) for i in range(N)])

canBattle = [-1] * N
D = [0] * N

while True:
    if not A:
        print(max(D))
        exit()

    i, a = A.popleft()
    if not a:
        continue
    if canBattle[i] != -1:
        A.append((i, a))
        continue
    j = a.popleft()

    if canBattle[j] == i:
        d = max(D[i], D[j])
        D[i], D[j] = d + 1, d + 1
        canBattle[i] = -1
        canBattle[j] = -1
    else:
        canBattle[i] = j

    if a:
        A.append((i, a))

print(-1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

    que = deque([i + 1 for i in range(N)])

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.append(a)
            now[a] = now[i] = 0
        else:
            now[i] = a

    for i in range(1, N + 1):
        if A[i]:
            print(-1)
            return
    print(max(days))


sol()
### BUGGY CODE ###

from collections import deque

s=deque(list( input() ))
t=deque([]) #

cnt=0
while len(s)>0:
  x=s.popleft()
  if len(t)>=2 and x=="C":
    if t[-2]=="A" and t[-1]=="B":
      cnt += 1
      t.pop()
      t.pop()
      s.appendleft("A")
      s.appendleft("C")
      s.appendleft("B")
    else:
      t.append(x)
  else:
    t.append(x)
        
#print(t,s)
print(cnt)

### FIXED CODE ###

from collections import deque

s=input()
s=s.replace("BC","D")
N=len(s)

cnt=0
cntA=0
cntD=0

for i in range(N):
  if s[i]=="A":
    cntA += 1
  elif s[i]=="D":
    cnt += cntA
  else:
    cntA=0
    cntD=0
    
print(cnt)
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():
    N, M = map(int,input().split())
    A = [int(input()) for _ in range(M)]


    dp = [0]*(N+1)
    dp[0]=1

    for i in range(N):
        if not i+1 in A:
            dp[i + 1] = (dp[i]+dp[i+1])%(10**9+7)
        if i < N - 1 and not i+2 in A:
            dp[i + 2] = (dp[i]+dp[i+2])%(10**9+7)
    print(dp[N]%(10**9+7))



resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

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


    dp=[1]*(N+1)
    for i in A:
        dp[i]=0

    for i in range(2,N+1):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)*dp[i]

    print(dp[N])

resolve()
### BUGGY CODE ###

from fractions import Fraction

import heapq

(m, n), aa = [list(map(int, s.split())) for s in open(0)]

aa = [-Fraction(a) for a in aa]

heapq.heapify(aa)

for _ in range(n):
    mx = heapq.heappop(aa)
    heapq.heappush(aa, mx / Fraction(2))

aa = [int(-a) for a in aa]

print(sum(aa))

### FIXED CODE ###

from fractions import Fraction
from math import log, ceil
import heapq

(n, m), aa = [list(map(int, s.split())) for s in open(0)]
aa = [-Fraction(a) for a in aa]

heapq.heapify(aa)

while m:
    m1 = heapq.heappop(aa)
#     print(f'{m=},{m1=}')
    if len(aa):
        m2 = aa[0]
        use = min(max(ceil(log(m1/m2)/log(2)), 1), m)
#         print(f'{m2=},{use=}')
    else:
        use = min(max(ceil(log(-m1)/log(2)), 1), m)
#         print(f'else, {use=}')
#         print(f'{ceil(log(-m1)/log(2))=}')
#     print(f'{m1/Fraction(2**use)}')
    heapq.heappush(aa, m1 / Fraction(2**use))
    m -= use
    if -(aa[0]) < 1:
        break

aa = [int(-a) for a in aa]

print(sum(aa))
### BUGGY CODE ###

from collections import deque, defaultdict
n, x, y = map(int, input().split())
x -= 1
y -= 1
edges = [[] for _ in range(n)]
edges[x].append(y)
edges[y].append(x)
for i in range(n-1):
    edges[i].append(i+1)
    edges[i+1].append(i)


def bfs(init_v):
    queue = deque([init_v])
    INF = 10**10
    dist = [INF]*n
    dist[init_v] = 0
    while queue:
        v = queue.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            queue.append(v2)
    return dist


dd = defaultdict(int)
for i in range(n):
    sp = bfs(i)
    for x in sp:
        dd[x] += 1

for i in range(1, n):
    print(dd[i]//2)


### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]

def shortest_path(i, j):
    if i <= x <= y <= j:
        return min(j-i, x-i+j-y+1)
    elif x <= i <= y <= j:
        return min(j-i, i-x+j-y+1)
    elif x <= i <= j <= y:
        return min(j-i, i-x+y-j+1)
    elif i <= x <= j <= y:
        return min(j-i, x-i+y-j+1)
    else:
        return j-i


ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = shortest_path(i, j)-1
        ans[path] += 1
print(*ans, sep="\n")
### BUGGY CODE ###

import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = int(input())

S = list()

for i in range(N):
    S.append(list(input()))
    S[i].sort()

ans = 0
for j in range(N):
    k = 1
    while j+k < N:
        if "".join(S[j]) == "".join(S[j+k]):
            ans += 1
        k += 1


print(ans)

### FIXED CODE ###

import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = int(input())

S = list()
num = {}
ans = 0

for i in range(N):
    S.append(list(input()))
    S[i].sort()
    if "".join(S[i]) in num:
        num["".join(S[i])] += 1
        ans += num["".join(S[i])]
    else:
        num["".join(S[i])] = 0

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

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

def input_int_array():
    return map(int, input().split())

MOD = 998244353

def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1

    for i in range(n):
        for j in range(k):
            l, r = spans[j]
            for lr in range(l, r + 1):
                if i + lr < n:
                    count[i + lr] = (count[i + lr] + count[i]) % MOD
                else:
                    break
    print(count[-1] % MOD)


answer()


### FIXED CODE ###

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

def input_int_array():
    return map(int, input().split())


MOD = 998244353


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0] * (n)
    count[0] = 1
    accum = [0] * (n + 1)
    accum[1] = 1

    for i in range(1, n):
        j = i + 1
        for l, r in spans:
            start = max(0, j - r - 1)
            end = max(0, j - l)
            count[i] += accum[end] - accum[start]
        accum[j] = accum[j-1] + count[i] % MOD
    print(count[n-1] % MOD)


answer()
### BUGGY CODE ###

N, K = map(int, input().split())
numgcd = [0]*(K+1)
for i in range(1, K+1)[::-1]:
    r = K//i
    num = r**N
    count = 2
    while count*i <= K:
        num = num - numgcd[count*i]
        count += 1
    numgcd[i] = num
sumgcd = 0
for j in range(1, K+1):
    sumgcd += j*numgcd[j]
mod = 10**9+7
print(sumgcd%mod)

### FIXED CODE ###

N, K = map(int, input().split())
numgcd = [0]*(K+1)
sumgcd = 0
mod = 10**9+7
for i in range(1, K+1)[::-1]:
    numgcd[i] = pow(K//i, N, mod)
    count = 2
    while count*i <= K:
        numgcd[i] -= numgcd[count*i]
        count += 1
    sumgcd += numgcd[i]*i
print(sumgcd%mod)
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
dp=[[0]*(len(s)+1) for i in range(4)]
dp[0][0]=1
lst="ABC"
for i in range(len(s)):
    for j in range(3):
        m1=1
        m2=0
        if s[i]=="?":
            m1=3
            m2=1
        
        if lst[j]==s[i]:
            m2=1
        
        dp[j][i+1]+=m1*dp[j][i]
        dp[j+1][i+1]+=m2*dp[j][i]
        dp[j][i]%=mod
        
    if s[i]=="?":
        dp[3][i+1]+=3*dp[3][i]
    else:
        dp[3][i+1]+=dp[3][i]
    dp[3][i]%=mod

print(dp[-1][-1]%mod)
# print(dp)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt,mod)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt,mod)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)
### BUGGY CODE ###

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

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

print(ans)

### FIXED CODE ###

from collections import Counter

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

l_sum = [0]
s= 0
for i in range(n):
    s += a[i]
    l_sum.append(s)

c_sum = Counter(l_sum)

# print(c_sum)
ans = 0
for i in c_sum:
    if c_sum[i] > 1:
        ans += c_sum[i] * (c_sum[i] - 1) // 2

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

def is_prime(num):
    if num<2:
        return False
    if num==2 or num==3:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True
 
def main():
    a,b=map(int,input().split())
    s,l=min(a,b),max(a,b)
    #sの約数のうち、素数を求める。
    s_sub=s
    #s_prime=[1]
    i=2
    ans=1
    while i<=s_sub:
        if s%i==0:
            if is_prime(i):
                if l%(i)==0:
                    ans+=1
                #s_prime.append(i)
                if is_prime(s//i):
                    if l%(s//i)==0:
                        ans+=1
                s_sub=s//i-1
        i+=1
        
    print(ans)
    
main()

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def is_prime(num):
    if num<1:
        return False
    if num==1 or num==2 or num==3:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True
 
def main():
    a,b=map(int,input().split())
    GCD=gcd(a,b)
    ans=0
    for i in range(1,int(GCD**0.5)+1):
        if GCD%i==0:
            if is_prime(i):
                ans+=1
            if i!=GCD and is_prime(GCD//i):
                ans+=1
    print(ans)
    
main()
### BUGGY CODE ###

mod = 10**9 + 7
t = input()
n = len(t)

l_a = [0] * (n + 1)
l_q = [0] * (n + 1)
r_c = [0] * (n + 1)
r_q = [0] * (n + 1)
total = 0

for i in range(1, n):
    l_a[i] = l_a[i - 1] + (1 if t[i - 1] == 'A' else 0)
    l_q[i] = l_q[i - 1] + (1 if t[i - 1] == '?' else 0)
for i in range(n - 1, 0, -1):
    r_c[i - 1] = r_c[i] + (1 if t[i] == 'C' else 0)
    r_q[i - 1] = r_q[i] + (1 if t[i] == '?' else 0)
for i in range(n):
    if t[i] in 'B?':
        total += l_a[i] * r_c[i] * 3**(l_q[i] + r_q[i]) + \
            l_a[i] * r_q[i] * 3**(l_q[i] + r_q[i] - 1) +\
            l_q[i] * r_c[i] * 3**(l_q[i] + r_q[i] - 1) +\
            l_q[i] * r_q[i] * 3**(l_q[i] + r_q[i] - 2)
        total %= mod
print(int(total))


### FIXED CODE ###

mod = 10**9 + 7
t = input()
n = len(t)

l_a = [0] * (n + 1)
l_q = [0] * (n + 1)
r_c = [0] * (n + 1)
r_q = [0] * (n + 1)
total = 0

for i in range(1, n):
    l_a[i] = l_a[i - 1] + (1 if t[i - 1] == 'A' else 0)
    l_q[i] = l_q[i - 1] + (1 if t[i - 1] == '?' else 0)
for i in range(n - 1, 0, -1):
    r_c[i - 1] = r_c[i] + (1 if t[i] == 'C' else 0)
    r_q[i - 1] = r_q[i] + (1 if t[i] == '?' else 0)


pow3mod = [1] * (n+1)
for i in range(n):
    pow3mod[i+1] = pow3mod[i] * 3 % mod

for i in range(n):
    if t[i] in 'B?':
        total += l_a[i] * r_c[i] * pow3mod[l_q[i] + r_q[i]] + \
            l_a[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_c[i] * pow3mod[l_q[i] + r_q[i] - 1] +\
            l_q[i] * r_q[i] * pow3mod[l_q[i] + r_q[i] - 2]
        total %= mod
print(int(total))
### BUGGY CODE ###

def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        for j in range(i,n):
            for k in range(j,n):
                if {s[i],s[j],s[k]}=={"R","G","B"} and j-i!=k-j:
                    ans+=1
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    s = input()
    r = [0] * n
    g = [0] * n
    b = [0] * n
    for i in range(n):
        if s[i] == "R":
            r[i] = 1
        elif s[i] == "G":
            g[i] = 1
        else:
            b[i] = 1
    ans = sum(r)*sum(g)*sum(b)

    for i in range(1, n // 2 + 1):
        j = 0
        while j + 2 * i <= n - 1:
            if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                ans -= 1
            j += 1
    print(ans)
resolve()
### BUGGY CODE ###

n,q = map(int, input().split())

tree = dict()
for i in range(n-1):
  a,b = map(int, input().split())
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for i in range(q):
  p,x = map(int, input().split())
  opr[p] += x

stack = [1]
parent = [0]*n
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x-1]: continue
    parent[y-1] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,q = map(int, input().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:n+n-2])
PX = iter(ABPX[n+n-2:])

tree = dict()
for a,b in zip(AB,AB):
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in zip(PX,PX):
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

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

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if g == 1:
    print(0); exit()
  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)
  

class union_find:
  def __init__(self, n):
    self.par = [-1] * n
  def __repr__(self):
    return "union_find({0})".format(self.par)
  def unite(self, x, y):
    if self.root(x) != self.root(y):
      self.par[self.root(x)] = y
  def root(self, x):
    if self.par[x] == -1:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  def same(self, x, y):
    return self.root(x) == self.root(y)

main()

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()
  if M == N-1:
    print(0); exit()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(y)
    if x == y: return
    if self.rank[x] < self.rank[y]: self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def root(self, x):
    if self.par[x] == -1: return x
    else: self.par[x] = self.root(self.par[x]); return self.par[x]
  def same(self, x, y): return self.root(x) == self.root(y)

main()
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            sa = j - i
            for k in range(j+1, n):
                if s[k] != s[j] and s[k] != s[i] and sa != k - j:
                    ans += 1
print(ans)


### FIXED CODE ###

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

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i
        if k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n = int(input())

    #output
    l = len(str(n))

    mod = 0
    for i in range(l):
        mod += int(str(n)[i])

    #  %%
    if mod % 9 == 0:
        print("Yes")
    else:
        print("No")

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

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n = str(input())

    #output
    l = len(n)

    mod = 0
    for i in range(l):
        mod += int(n[i])
        mod %= 9 

    #  %%
    if mod == 0:
        print("Yes")
    else:
        print("No")

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

S = input()
count = 0
for i in range(len(S) - 3):
    for j in range(i+5, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

S = input()
mod = 2019

cs_mods = {0:1}
cumsum = 0
count = 0
for i, s in enumerate(S[::-1]):
    cumsum = (cumsum + int(s) * pow(10, i, mod)) % mod
    cs_mods.setdefault(cumsum, 0)
    # count += cs_mods[cumsum]
    cs_mods[cumsum] += 1

# count = 0
for k, v in cs_mods.items():
    count += v*(v-1)//2

print(count)
### BUGGY CODE ###

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

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



### FIXED CODE ###

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

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)