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

def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))
### BUGGY CODE ###

import heapq

INF = 10**30
n = int(input())
dist_mat = [[INF]*n for _ in range(n)]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    dist_mat[a][b] = c
    dist_mat[b][a] = c
    edges[a].append(b)
    edges[b].append(a)
    dist_mat[i][i] = 0

q, k = map(int, input().split())
k -= 1

que = [(0, k)]
heapq.heapify(que)
costs = [INF]*n
costs[k] = 0
while len(que) > 0:
    dist, current = heapq.heappop(que)
    for edge in edges[current]:
        if costs[edge] > costs[current] + dist_mat[current][edge]:
            costs[edge] = costs[current] + dist_mat[current][edge]
            heapq.heappush(que, (costs[edge], edge))

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

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

q, k = map(int, input().split())
k -= 1
costs[k] = 0
dfs(k)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)
### BUGGY CODE ###

import sys


def solve(l, r, primeset):
    res = 0
    for i in range(l, r + 1, 2):
        if i in primeset and (i + 1) // 2 in primeset:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [2]
    A = 10 ** 5 + 10
    for L in range(3, A, 2):
        if all(L % L2 != 0 for L2 in primelist):
            primelist.append(L)
    primeset = set(primelist)
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primeset))


if __name__ == "__main__":
    main()


### FIXED CODE ###

MAX = 10 ** 5 + 1
f = [True] * (MAX)
c = [0] * (MAX + 1)
for i in range(2, MAX):
    if f[i]:
        for j in range(i + i, MAX, i):
            f[j] = False
for i in range(3, MAX, 2):
    if f[i] and f[(i + 1) // 2]:
        c[i] += 1
for i in range(3, MAX):
    c[i] += c[i - 1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l - 1])
### BUGGY CODE ###

from itertools import product
 
n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")
 
for i, j, l, m in product(range(n), repeat=4):
    cnt = 0
    for g in range(n):
        if p[i][0] <= p[g][0] <= p[j][0] and p[l][1] <= p[g][1] <= p[m][1]:
            cnt += 1
    if cnt >= k:
        ans = min(ans, (p[j][0] - p[i][0]) * (p[m][1] - p[l][1]))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

p.sort()
for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = p[j][0] - p[i][0]
        yl = sorted(p[i:j+1],key=lambda x:x[1])
        for l in range(len(yl)-k+1):
            y = yl[l+k-1][1] - yl[l][1]
            ans = min(ans, y*x)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)

def get3(x):
  r1 = a[x]
  r2 = []
  for u in r1:
    r2 += a[u]
  r3 = []
  m = [False] * (N+1)
  for u in r2:
    for v in a[u]:
      if not(m[v]):
        m[v] = True
        r3.append(v)
  return r3
  
S, T = map(int, input().split())
def main():
  c = [S]
  m = [False] * (N+1)
  for count in range(1, N+1):
    vs = []
    for u in c:
      m[u] = True
      vs += get3(u)
    c = []
    for v in vs:
      if (v == T):
        return count
      if not(m[v]):
        c.append(v)
  return -1
print(main())


### FIXED CODE ###

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          m[v][(count+1) %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())
### BUGGY CODE ###

L=list(map(int,input().split()))
N=L[0]
K=L[1]
Q=L[2]
S=[]
for i in range(Q):
  S.append(int(input()))
point=[0]*N
num_ans=[0]*N
for i in range(N):
  num_ans[i]=S.count(i+1)
  point[i]=K-Q+num_ans[i]
  if point[i]>0 :
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

L=list(map(int,input().split()))
N=L[0]
K=L[1]
Q=L[2]
point=[K-Q]*N
for i in range(Q):
  ans=int(input())
  point[ans-1]+=1
for i in range(N):
  if point[i]>0 :
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

D = [0] * (n+1)
P = [0] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
        for t in T[i]:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [set() for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].add(a)

D = [0] * (n+1)
P = [0] * (n+1)
used = [0] * (n+1)

def dfs(p, i, depth):
    if used[i]:
        return None
    D[i] = depth
    P[i] = p
    used[i] = True
    for t in tuple(T[i]):
        RT[t].remove(i)
    for t in tuple(T[i]):
        if not RT[t]:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(tuple(RT[i])[0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)
### BUGGY CODE ###

# coding:utf-8

N, K = map(int, input().split())
H = [int(hi) for hi in input().split()]
dp = [0]*N

for i in range(1, K+1):
    if i > N-1:
        break
    dp[i] = abs(H[0]-H[i])

for i in range(K+1, N):
    dp[i] = min([dp[i-j]+abs(H[i-j]-H[i]) for j in range(1, K+1)])
    

print(dp[N-1])

### FIXED CODE ###

# coding:utf-8

N, K = map(int, input().split())
H = [int(hi) for hi in input().split()]
dp = [0]*(N+1)


for i in range(1, K+1):
    if i <= N-1:
        dp[i] = abs(H[0]-H[i])

for i in range(K+1, N):
    dp[i] = min([dpk + abs(hk - H[i]) for dpk, hk in zip(dp[i-K:i], H[i-K:i])])


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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())

count = 0
for i in range(1,N):
    count += len(make_divisors(N-i))
print(count)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

N = int(input())
A = [0] + [int(_) for _ in input().split()]
B = [0]
is_monotone = True
for i in range(N):
    if is_monotone:
        is_monotone &= A[i + 1] > A[i]
    B += [min(A[i + 1], 18)]
if is_monotone:
    print(1)
    exit()


def is_possible(K):
    mp = {}
    for i in range(N):
        if A[i] >= A[i + 1]:
            for key in sorted(mp.keys(), reverse=True):
                if key >= A[i + 1]:
                    del mp[key]
                else:
                    break
            flag = True
            for j in range(A[i + 1] - 1, -1, -1):
                if mp.get(j, 0) < K - 1:
                    mp[j] = mp.get(j, 0) + 1
                    flag = False
                    break
                elif j in mp:
                    del mp[j]
            if flag:
                return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))


### FIXED CODE ###

import random
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    if index <= array[0][0]:
        return [(index, array[0][1])]
    for _ in range(len(array)-1, 0, -1):
        if array[_ - 1][0] < index:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))
### BUGGY CODE ###

n = int(input())
a  = list(input().split())
ans = a[0]
for i in range(1, n):
	if i%2==n%2:
		ans += " " + a[i]
	else:
		ans = a[i] + " " + ans
print(ans)

### FIXED CODE ###

n=int(input())
a=list(input().split())
print(" ".join(a[::-2]+a[n%2::2]))
### BUGGY CODE ###

import sys

def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v

# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))

# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x > n: break
    g.append(x)
    m += 1
g = g[::-1]

# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))

# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])

# 3 output cnt
print(cnt)
# 4 output sorted a
for i in range(n):
    print(a[i])

### FIXED CODE ###

import sys
 
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
 
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
 
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
 
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
 
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
 
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def main():
    N = 10**5+1
    ps = primes(N)
    P = [0]*N
    for p in ps:
        P[p] = 1

    Q = int(input())
    for _ in range(Q):
        ans = 0
        l,r = map(int, input().split())
        for i in range(l, r+1):
            if P[i] and P[(i+1)//2]:
                ans += 1
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def main():
    N = 10**5+1
    ps = primes(N)

    P = [0]*N
    for p in ps:
        P[p] = 1

    ruisekiwa = [0]*N
    for i in range(3, N, 2):
        if P[i] and P[(i+1)//2]:
            ruisekiwa[i] = 1
    for i in range(3, N):
        ruisekiwa[i] += ruisekiwa[i-1]
    
    Q = int(input())
    for _ in range(Q):
        l,r = map(int, input().split())
        ans = ruisekiwa[r] - ruisekiwa[l-1]
        print(ans)

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

n,q=map(int,input().split())
s=input()
for i in range(q):
    li,ri=map(int,input().split())
    print(s[li-1:ri].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
cnt=[0]*n
icnt=0
for i in range(n-1):
#    print(s[i:i+2])
    if s[i:i+2]=="AC":
      icnt=icnt+1
      cnt[i+1]=cnt[i]+1
    else:
      cnt[i+1]=cnt[i]
#print(cnt,s)
for i in range(q):
    li,ri=map(int,input().split())
#    print(s[li-1:ri].count("AC"))
#    print(sum(cnt[li-1:ri-1]))
    print(cnt[ri-1]-cnt[li-1])
### BUGGY CODE ###

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

edges = []
toE = [[] for _ in range(N)]
frE = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    toE[fr].append(to)
    frE[to].append(fr)

def getVisitedList(s, edges):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        now = st.pop()
        for to in edges[now]:
            if not visited[to]:
                visited[to] = True
                st.append(to)
    return visited

canGo = getVisitedList(0, toE)
canBack = getVisitedList(N - 1, frE)

def sol():
    minDist = [10**18] * N
    minDist[0] = 0
    for i in range(N + 1):
        for fr, to, c in edges:
            d = minDist[fr] + c
            if minDist[to] > d:
                if i == N and canGo[fr] and canBack[to]:
                    return -1
                minDist[to] = d
    return max(0, -minDist[N - 1])

print(sol())


### FIXED CODE ###

N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

print(max(0, -minDist[N - 1]))
### BUGGY CODE ###

n = int(input())

lis = [i for i in range(1, n+1)]
print(sum(lis[:-1]))

### FIXED CODE ###

n = int(input())

print((n*(n-1)//2))
### BUGGY CODE ###

def roop(now, a_list):
    return a_list[now-1]

if __name__ == '__main__':
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    
    now = 1
    check = [1]
    for i in range(k):
        now = roop(now, a_list)
        if now not in check:
            check.append(now)
        else: 
            break

    point = (check.index(now))
    roop_len = len(check) - point

    if k <= len(check):
        print(check[k])
    else:
        k_ = k - point
        point_ = k_ % roop_len
        print(check[point+point_])

### FIXED CODE ###

if __name__ == '__main__':
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    
    now = 1
    check = [0] * n
    check[0] = 1
    move = [1]
    for i in range(k):
        now = a_list[now-1]
        move.append(now)
        if check[now-1] == 0:
            check[now-1] = 1
        else: 
            break

    point = (move.index(now))
    roop_len = sum(check) - point

    if k <= sum(check):
        print(move[k])
    else:
        k_ = k - point
        point_ = k_ % roop_len
        print(move[point+point_])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()

            if not group[node]:
                group[node] = count
    
            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

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

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    #print(a)

    sum = 0
    for i in range(n):
        root = list([0])
        for j in range(n):
            if j!=i:
                root.append(a[j])
        root.append(0)
        #print(root)
        for j in range(1, n+1):
            sum += abs(root[j]-root[j-1])
        print(sum)
        sum = 0


### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    A = list([0])
    A.extend(a)
    A.append(0)

    sum = 0
    for i in range(1, n+2):
        sum += abs(A[i]-A[i-1])
    for i in range(1, n+1):
        print(sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

def dfs(s, n, m):
    if n > m:
        return m
    elif s.find('WR') == -1:
        return n
    else:
        w_count = s.count('W')
        r_count = s.count('R')
        m = min(w_count, r_count)

        i, j = 0, -1
        while True:
            if s[j] == 'R':
                break
            else:
                j -= 1

        while True:
            if s[i] == 'W':
                break
            else:
                i += 1

        s = list(s)
        s[i] = 'R'
        s[j] = 'W'
        s = ''.join(s)
        return min(dfs(s, n+1, m), m)

N = int(input())
s = input()
print(dfs(s, 0, len(s)))

### FIXED CODE ###

from collections import Counter
N = int(input())
s = input()
c = Counter(s)
w, r = 0, c['R']
ans = max(w, r)
for i in range(N):
    if s[i] == 'W': w += 1
    else: r -= 1 
    ans = min(ans, max(w, r))

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

N, P = 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)
    import sys
    sys.exit(0)

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
for num in suf_nums[::-1]:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)



### FIXED CODE ###

N, P = 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)
    import sys
    sys.exit(0)

surpluses = [0] * P
s = 0
power = 1
for i in range(N):
    s = (s + int(S[-1-i]) * power) % P
    surpluses[s % P] += 1
    power = (power * 10) % P

ans = surpluses[0]
for count in surpluses:
    ans += count * (count - 1) // 2

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

if __name__ == '__main__':
	N = int(input())
	ls = [int(a) for a in input().split()]
	c = 0
	for i in range(N):
		h = ls[i]
		r = i+h+1
		if r < N:
			for j in range(r,N):
				H = ls[j]
				if h+H == abs(j-i):
					c += 1	

	print(c)

### FIXED CODE ###

if __name__ == '__main__':
	N = int(input())
	ls = [int(a) for a in input().split()]
	c = 0
	dic = {}
	for i in range(N):
		h = ls[i]
		if i > 0:
			c += dic.get(i-h,0)
		v = dic.get(i+h,0)
		if v == 0:
			dic[i+h] = 1
		else:
			dic[i+h] += 1

	print(c)