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

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp = 0
        pre_dp_i = dp[i][0]
        for j, t in enumerate(T):
            dp_i = dp[i][j+1]
            pre_dp = max((pre_dp_i + 1) * (s == t),
                         dp_i,
                         pre_dp)
            dp[i + 1][j + 1] = pre_dp
            pre_dp_i = dp_i
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	skill = []
	for _ in range(Q):
		t, d = input().split(" ")
		skill.append((t, d))
	
	gorlm_num = [1] * len(S)
	
	for i, val in enumerate(skill):
		t, d = val
		#print(gorlm_num)
		for j, vol in enumerate(S):
			if t == vol:
				if d == "R" and gorlm_num[j] > 0:
					tt = gorlm_num[j]
					gorlm_num[j] = 0
					if j != len(S)-1:
						gorlm_num[j+1] += tt
				if d == "L" and gorlm_num[j] > 0:
					tt = gorlm_num[j]
					gorlm_num[j] = 0
					if j != 0:
						gorlm_num[j-1] += tt
						
	ans = 0
	for i in gorlm_num:
		ans = ans + i
		
	print(ans)
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
	
def main():
	N, Q = map(int, input().split())
	S = "_" + input() + "_"
	
	TD = []
	for _ in range(Q):
		tmp = input().split(" ")
		t = tmp[0]
		d = tmp[1]
		TD.append((t, d))
		
	TD.reverse()
	gake_L = 0
	gake_R = N - 1 + 2
	
	for i, val in enumerate(TD):
		t, d = val
		
		if d == "R":
			if t == S[gake_R-1]:
				gake_R -= 1
			if t == S[gake_L]:
				gake_L -= 1
		
		if d == "L":
			if t == S[gake_R]:
				gake_R += 1
			if t == S[gake_L+1]:
				gake_L += 1
	
	print(max(0, gake_R-gake_L-1))
	
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

def warshall_floyd(dist):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k] + dist[k][j])
    return dist

n, m, l = map(int, input().split()) #N:頂点数　M:辺の数 L:容量
dist = [[float("inf") for i in range(n)] for j in range(n)]

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

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

warshall_floyd(dist)
dist2 = [[float("inf") for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

warshall_floyd(dist2)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]-1
    if dist2[s-1][t-1] == float("inf"):
        ans = -1
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

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

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


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

import math
k = int(input())
s = len(input())

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)


### FIXED CODE ###

import math
k = int(input())
s = len(input())

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)
### BUGGY CODE ###

input()
da = list(map(int,input().split()))
da.insert(0,0)
al = 0
if da[0] == 0:
  al += 0
for k in range(1,len(da)):
  da[k] += da[k-1]
  if da[k]== 0:
        al += 1
for i in range(1,len(da)):
    for j in range(1,len(da)-i):
      if da[i+j] - da[i] == 0:
        al += 1
print(al)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = [int(i) for i in input().split()]
 
s = 0
d = defaultdict(int)
ans = 0
d[0] = 1
 
for i in a:
    s += i
    ans += d[s]
    d[s] += 1
 
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = np.array(A)
for n in range(N):
    ind_rm = [n]
    ind = np.ones(N, dtype=bool)
    ind[ind_rm] = False
    print(max(A[ind]))

### FIXED CODE ###

import numpy as np
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = np.array(A)
all_max = np.max(A)
max_ind = np.argmax(A)
max_remove = np.ones(N, dtype=bool)
max_remove[max_ind] = False
second_max = np.max(A[max_remove])
# print(all_max)
# print(second_max)
for n in range(N):
    if n == max_ind:
        print(second_max)
    else:
        print(all_max)
### BUGGY CODE ###


def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

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

mod = 10**9 + 7

s = [2]
now = 3
dic = {}

while now ** 2 <= 10 ** 6:

    flag = True
    for i in s:
        if now % i == 0:
            flag = False
            break

    if flag:
        s.append(now)
    now += 2

for i in s:
    dic[i] = 0

for a in A:

    for j in s:
        cnt = 0
        while a % j == 0:
            cnt += 1
            a //= j

        dic[j] = max(dic[j],cnt)

    if a != 1:
        s.append(a)
        dic[a] = 1

lcm = 1

for i in s:
    for j in range(dic[i]):
        lcm *= i
        lcm %= mod

ans = 0
for i in range(N):
    ans += lcm * inverse(A[i],mod)
    ans %= mod
print (ans)


### FIXED CODE ###

import fractions

def lcm(x,y):
  return x // fractions.gcd(x,y) * y


mod = 10**9+7


N = int(input())

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

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

for i in range(N):
    g = lcm(g,A[i])

print (g * B % mod)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

bit = Bit(n + 1)
bit.add(1, 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1))

print(bit.sum(n + 1))


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

bit = Bit(n + 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1) + 1)

print(bit.sum(n + 1) + 1)
### BUGGY CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=np.uint32)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = mat[::-1]
matmul = np.cumsum(mat, axis=0)
matmul = matmul[::-1]
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)

### FIXED CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=int)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)
### BUGGY CODE ###

def z_algo(S):
    '''
    Input: a string S
    Output: an array Z[0..|S| - 1]
            Z[i] = l: the length of the longest prefix of S[i..|S| - 1] which is also a prefix of S,
            i.e.,
                S[j] = S[i + j] for all 0 <= j < l (l != 0),
                S[0] != S[i] (l == 0)
    Time complexity: O(|S|) time
    '''
    N = len(S)
    Z = [-1] * N
    Z[0] = N
    L = 0; R = 0 # algorithm invariant: S[L..R] is always set to be the longest common prefix of S[L..|S| - 1]
    for i in range(1, N):
        if i > R: # naive calculation
            j = 0
            while i + j < N and S[j] == S[i + j]: j += 1
            Z[i] = j
            if j > 0: L = i; R = i + j - 1
        else: # i in [L, R]
            k = i - L
            if Z[k] < R - i + 1: Z[i] = Z[k]
            else:
                L = i
                while R < N and S[R - L] == S[R]: R += 1
                Z[i] = R - L
                R -= 1
    return Z

N = int(input())
S = input()
ans = 0
for i in range(N-1):
    Z = z_algo(S[i:])
    for j, z in enumerate(Z[1:], 1):
        ans = max(ans, min(z, j))
print(ans)

### FIXED CODE ###

def z_algo(S):
    '''
    Input: a string S
    Output: an array Z[0..|S| - 1]
            Z[i] = l: the length of the longest prefix of S[i..|S| - 1] which is also a prefix of S,
            i.e.,
                S[j] = S[i + j] for all 0 <= j < l (l != 0),
                S[0] != S[i] (l == 0)
    Time complexity: O(|S|) time
    '''
    N = len(S)
    Z = [-1] * N
    Z[0] = N
    L = 0; R = 0 # algorithm invariant: S[L..R] is always set to be the longest common prefix of S[L..|S| - 1]
    for i in range(1, N):
        if i > R: # naive calculation
            j = 0
            while i + j < N and S[j] == S[i + j]: j += 1
            Z[i] = j
            if j > 0: L = i; R = i + j - 1
        else: # i in [L, R]
            k = i - L
            if Z[k] < R - i + 1: Z[i] = Z[k]
            else:
                L = i
                while R < N and S[R - L] == S[R]: R += 1
                Z[i] = R - L
                R -= 1
    return Z

N = int(input())
S = input()
ans = 0
for i in range(N-1):
    Z = z_algo(S[i:])
    for j, z in enumerate(Z):
        ans = max(ans, min(z, j))
print(ans)
### BUGGY CODE ###

import functools
import operator

N,K = map(int,input().split())
A = list(map(int,input().split()))
R = []
for i in range(N-K+1):
  X = functools.reduce(operator.mul,A[i:i+K])
  R.append(X)
  if i ==0:
    continue
  else:
    if X > R[i-1]:
      print("Yes")
    else:
      print("No")


### FIXED CODE ###

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

for i in range(K-1,N-1):
  if A[i-(K-1)] < A[i+1]:

    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

table = list(range(2, max_r+1))
prime_table = []
while True:
    prime_num = table.pop(0)
    prime_table.append(prime_num)
    table = [ i for i in table if i % prime_num != 0]
    if len(table) == 0:
        break

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if odd in prime_table and (odd+1)//2 in prime_table:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])


### FIXED CODE ###

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

MAX_X = 100030
prime_table = [True] * MAX_X
prime_table[0] = prime_table[1] = False

for (i, is_prime) in enumerate(prime_table):
    if is_prime:
        for n in range(i*i, MAX_X, i):
            prime_table[n] = False

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if prime_table[odd] and prime_table[(odd+1)//2]:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])
### BUGGY CODE ###

def main():
    S = input()
    multipuls = []
    answers = []

    # 事前に2019の倍数を作っておいた方がコスト削減になるかと思ったが、
    # あまり意味がない気がしてきたのでやめる
    # i = 1
    # while True:
    #     if 2019 * i > 200000:
    #         break
    #     multipuls.append(2019 * i)
    #     i += 1

    for i in range(len(S) - 1):
        for j in range(i + 3, len(S)):
            # print(S[i:j+1])
            # print(i + 1, j + 1)
            if int(S[i:j+1]) % 2019 == 0:
                answers.append((i + 1, j + 1))

    print(len(answers))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot = (tot + (int(S[i]) * x)) % 2019
        ans += cnt[tot]
        x = (x * 10) % 2019
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


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

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

res = abs(sum(a[0:1]) - sum(a[1:]))
for i in range(2, N-1):
  temp_a = sum(a[0:i])
  temp_b = sum(a[i:])
  if abs(temp_a - temp_b) < res:
  	res = abs(temp_a - temp_b)
print(res)

### FIXED CODE ###

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

for i in range(1, N):
  a[i] += a[i-1]

res = abs(a[0] - (a[-1]-a[0]))
for i in range(N-1):
  res = min(res, abs(a[i] - (a[-1] - a[i])))

print(res)
### BUGGY CODE ###

inf = 10 ** 18

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [inf for _ in range(h + max_a)]
dp[0] = 0
for i in range(1, h + max_a):
    min_dp = inf
    for a, b in ab:
        if 0 > i - a:
            continue
        min_dp = min(min_dp, dp[i-a] + b)
    dp[i] = min_dp
print(min(dp[h:]))


### FIXED CODE ###

inf = 10 ** 18
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [inf] * (h + max_a)
dp[0] = 0
for i in range(1, h + max_a):
    dp[i] = min(dp[i-a] + b for a, b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

S = input()
T = input()

min_dist = 10**10
for i in range(len(S) - len(T) + 1):
    for k in range(len(T)):
        dist = sum(s != t for s, t in zip(S[i:i + len(T)], T))
        min_dist = min(dist, min_dist)
        if min_dist == 0:
            print(0)
            exit()

print(min_dist)


### FIXED CODE ###

S = input()
T = input()

min_dist = 10**10
for i in range(len(S) - len(T) + 1):
    for k in range(len(T)):
        dist = 0
        for s, t in zip(S[i:i + len(T)], T):
            if s != t:
                dist += 1
            if dist >= min_dist:
                break

        min_dist = min(dist, min_dist)
        if min_dist == 0:
            print(0)
            exit()

print(min_dist)
### BUGGY CODE ###

from pprint import pprint
import sys
sys.setrecursionlimit(10**7) 

N = int(input())
An = [int(_) for _ in input().split()]

ans = 1;
for i in An:
    ans = ans * i
    
if(ans > 10**18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys

N = int(input())

An = [int(_) for _ in input().split()]
An.sort()

ans = 1

for val in An:
    # 0がきたらすぐに抜ける
    if(int(val) == 0):
        print(0)
        sys.exit()
    ans *= val
    # ansが10^18を超えた時点で-1にする
    if(ans > 10 **18):
        print(-1)
        sys.exit()

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

MALE = 0
FEMALE = 1

def query(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()

    if s == 'Male':
        return(MALE)
    else:
        return(FEMALE)

def search(start, end, start_gendar):
    i = (end - start)//2
    g = query(start + i)
    if (i%2 == 0 and g != start_gendar) or (i%2 != 0 and g == start_gendar):
        return (start, i, start_gendar)
    return (i, end, g)

def main():
    n = int(input())
    start = 0
    end = n
    gendar = query(0)
    for i in range(20):
        start_new, end_new, gendar_new = search(start, end, gendar)
        start = start_new
        end = end_new
        gendar = gendar_new

if __name__ == "__main__":
    main()

### FIXED CODE ###

MALE = 0
FEMALE = 1

def query(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()

    if s == 'Male':
        return(MALE)
    else:
        return(FEMALE)

def search(start, end, start_gendar):
    i = (end - start)//2
    g = query(start + i)
    if (i%2 == 0 and g != start_gendar) or (i%2 != 0 and g == start_gendar):
        return (start, start+i, start_gendar)
    return (start+i, end, g)

def main():
    n = int(input())
    start = 0
    end = n
    gendar = query(0)
    for i in range(20):
        start_new, end_new, gendar_new = search(start, end, gendar)
        start = start_new
        end = end_new
        gendar = gendar_new

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

def main():
    N=int(input())
    c=input()
    
    #x...WR
    #o...RR, RW, WW
    #Wが来たらそれ以降はW
    #R(0個以上)+W(0個以上)
    
    i=0
    for _ in range(N):
        if 'WR' in c:
            x=c.index('WR')  
            y=N-c[::-1].index('R')-1
            #print(x,y)
            c=c[:x]+'R'+c[x+1:y]+'W'+c[y+1:]
            #print(c)
            i+=1
            
    print(min(c.count('R'),c.count('W'),i))
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N=int(input())
    c=list(input())
    
    #x...WR
    #o...RR, RW, WW
    #Wが来たらそれ以降はW
    #R(0個以上)+W(0個以上)
    
    res=0
    cR=c.count('R')
    cW=c.count('W')
    
    l,r=0,N-1
    while l!=r:
        if c[l]=='W':
            if c[r]=='R':
                c[l],c[r]='R','W'
                res+=1
            else:
                r-=1
        else:
            l+=1
        
    print(min(cR,cW,res))
    
 
if __name__ == '__main__':
    main()