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

import sys

def insert(heap, key):
    heap.append(-1000000)
    heapIncreaseKey(heap, key)

def parent(i):
    return (i - 1) // 2

def heapIncreaseKey(heap, key):
    heap[len(heap) - 1] = key
    i = len(heap) - 1
    while i > 0 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

def heapExtractMax(heap):
    if len(heap) < 1:
        return None
    else:
        MAX = heap[0]
        heap[0] = heap.pop()
        maxHeapify(heap, 0)

        return MAX

def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)


heap = []
while True:
    line = sys.stdin.readline()
    if line[0] == 'i':
        insert(heap, int(line.split()[1]))
    elif line[0:2] == 'ex':
        print(str(heapExtractMax(heap)))
    else:
        break

### FIXED CODE ###

from sys import stdin
from heapq import heappop, heappush
readline = stdin.readline

heap = []
while True:
    line = readline()
    if line[1] == 'x':
        print(-heappop(heap))
    elif line[0] == 'i':
        heappush(heap, -int(line.split()[1]))
    else:
        break


'''
def insert(heap, key):
    heap.append(-1000000)
    heapIncreaseKey(heap, key)

def parent(i):
    return (i - 1) // 2

def heapIncreaseKey(heap, key):
    heap[len(heap) - 1] = key
    i = len(heap) - 1
    while i > 0 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

def heapExtractMax(heap):
    if len(heap) < 1:
        return None
    else:
        MAX = heap[0]
        heap[0] = heap.pop()
        maxHeapify(heap, 0)

        return MAX

def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)


heap = []
while True:
    line = sys.stdin.readline()
    if line[0] == 'i':
        insert(heap, int(line.split()[1]))
    elif line[0:2] == 'ex':
        print(str(heapExtractMax(heap)))
    else:
        break
'''
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
q=int(input())
A=[]
b=0
def f(A,b,n):
  res=0
  for a in A:
    res+=abs(a-n)
  return res+b
for _ in range(q):
  L=[int(i) for i in input().split()]
  if L[0]==1:
    n=bisect.bisect_left(A,L[1])
    A.insert(n,L[1])
    b+=L[2]
  else:
    n=A[(len(A)-1)//2]
    print(n,f(A,b,n))


### FIXED CODE ###

from heapq import heappop
from heapq import heappush
q=int(input())
L,R=[],[]
b_sum=0
l_sum,r_sum=0,0
count=0
mid=0
for _ in range(q):
  
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    count+=1
    b_sum+=b
    if count==1:
      mid=a
    elif count%2==0:
      if a<=mid:
        heappush(L,-a)
        l_sum+=a
        heappush(R,mid)
        r_sum+=mid
      else:
        heappush(L,-mid)
        l_sum+=mid
        heappush(R,a)
        r_sum+=a
    else:
      l,r=-heappop(L),heappop(R)
      if a<l:
        heappush(L,-a)
        l_sum+=a-l
        mid=l
        heappush(R,r)
      elif r<a:
        heappush(L,-l)
        mid=r
        heappush(R,a)
        r_sum+=a-r
      else:
        heappush(L,-l)
        mid=a
        heappush(R,r)

  else:
    if count%2==1:
      print(mid,r_sum-l_sum+b_sum)
    else:
      l=-heappop(L)
      print(l,r_sum-l_sum+b_sum)
      heappush(L,-l)
### BUGGY CODE ###

import collections
N = int(input())

counter = collections.Counter([input() for _ in range(N)])

answers = [k for k, v in counter.items() if v == max(counter.values())]
answers.sort()
for x in answers:
  print(x)

### FIXED CODE ###

import collections
N = int(input())
counter = collections.Counter([input() for _ in range(N)])
maximum = max(counter.values())
answers = [k for k, v in counter.items() if v == maximum]
answers.sort()
for x in answers:
  print(x)
### BUGGY CODE ###

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    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])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

pattern = "AC"
N, Q = map(int, input().split(" "))
S = input()
for i in range(Q) :
    l, r = map(int, input().split(" "))
    print(S[l-1:r].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()

ACIndex = [0] * (N+1)
for i in range(N) :
    ACIndex[i+1] = ACIndex[i] + (1 if S[i:i+2] == "AC" else 0)

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

import numpy as np
from math import factorial

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

dic = {}
after = {}

newdata = np.unique(A)
for i in range(len(newdata)):
	x = np.sum(A == newdata[i])
	dic[newdata[i]] = x * (x - 1) // 2
	after[newdata[i]] = (x - 1) * (x - 2) // 2

numsum = 0
for dicv in dic.values():
	numsum += dicv 

ans = {}
for key in dic.keys():
	ans[key] = numsum - dic[key] + after[key]

for i in range(N):
	print(ans[A[i]])



### FIXED CODE ###

import numpy as np
import collections

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

dic = {}
after = {}

l = collections.Counter(A)

for key, val in l.items():
	dic[key] = val * (val - 1) // 2
	after[key] = (val - 1) * (val - 2) // 2

numsum = sum(dic.values())

ans = {}
for key in dic.keys():
	ans[key] = numsum - dic[key] + after[key]

for i in range(N):
	print(ans[A[i]])
### BUGGY CODE ###

A=int(input())
l=list(map(int,input().split()))
n=set()
for i in range(A-1):
    n.add(abs(sum(l[:i+1])-sum(l[i+1:])))
print(min(n))

### FIXED CODE ###

A=int(input())
l=list(map(int,input().split()))
right=l[0]
left=sum(l[1:])
ans=left-right
for i in range(A-2):
    right+=l[i+1]
    left-=l[i+1]
    ans=min(ans,abs(right-left))
print(ans)
### BUGGY CODE ###

n = int(input())

ans = []
for i in range(n):
    c = input().split()
    cmd = c[0]
    x = 0
    if 1 < len(c):
        x = int(c[1])
    if cmd == 'insert':
        y = [x] + ans
        ans = y
    elif cmd == 'delete':
        try:
            index = ans.index(x)
            ans.pop(index)
        except:
            ''
    elif cmd == 'deleteFirst':
        ans.pop(0)
    elif cmd == 'deleteLast':
        ans.pop(len(ans) - 1)

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

### FIXED CODE ###

import sys
from collections import deque
n = int(sys.stdin.readline())

ans = deque()

for i in range(n):
    c = sys.stdin.readline()[:-1]
    if c[0] == 'i':
        ans.appendleft(c[7:])
    elif c[6] == ' ':
        try:
            ans.remove(c[7:])
        except:
            pass
    elif c[6] == 'F':
        ans.popleft()
    else:
        ans.pop()

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

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


S_R = []
S_G = []
S_B = []


for i in range(N):
    s = S[i]
    if (s == 'R'):
        S_R.append(i)
    if (s == 'G'):
        S_G.append(i)
    if (s == 'B'):
        S_B.append(i)

count = 0

for i in S_R[::1]:
    for j in S_G[::1]:
        for k in S_B[::1]:
            if(i < j < k):
                if(j - i != k - j):
                    count += 1
            if (i < k < j):
                if (k - i != j - k):
                    count += 1
            if (j < i < k):
                if (i - j != k - i):
                    count += 1
            if (j < k < i):
                if (k - j != i - k):
                    count += 1
            if (k < i < j):
                if (i - k != j - i):
                    count += 1
            if (k < j < i):
                if (j - k != i - j):
                    count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

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

saidai = 0

for i in range (n):
    count = 0
    for j in range (n-i-1):
        if int(h[i+j])>=int(h[i+j+1]):
            count = count+1
        else :
            break
    saidai = max(saidai,count)

print(saidai)


### FIXED CODE ###

n=int(input())
h = list(map(int,input().split()))
m=0
count = 0

for i in range (n-1):
    if h[i]>=h[i+1]:
        count += 1
    else:
        m = max(m,count)
        count = 0
m = max(m,count)
print(m)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
S = input()

dic = defaultdict(list)
for i in range(N):
    dic[S[i]].append(int(i))

count = 0
for i in range(N-1):
    for j in range(i+1,N):
        if S[i] == "R" and S[j] == "G":
            for k in dic["B"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

        elif S[i] == "R" and S[j] == "B":
            for k in dic["G"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

        elif S[i] == "G" and S[j] == "B":
            for k in dic["R"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

        elif S[i] == "G" and S[j] == "R":
            for k in dic["B"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

        elif S[i] == "B" and S[j] == "R":
            for k in dic["G"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

        elif S[i] == "B" and S[j] == "G":
            for k in dic["R"]:
                if i < j and j < k and (j-i != k-j):
                   count += 1

print(count)   

### FIXED CODE ###

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

rcount = S.count("R")
gcount = S.count("G")
bcount = N-rcount-gcount



count = rcount * gcount * bcount
k = 0
for i in range(N-1):
    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]:
                count -= 1
print(count)
### BUGGY CODE ###

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
CD = [list(map(int, input().split())) for i in range(K)]

friends = {i:set() for i in range(1, N+1)}

for a, b in AB:
    friends[a].add(b)
    friends[b].add(a)

blocks = {i:set() for i in range(1, N+1)}
for c, d in CD:
    blocks[c].add(d)
    blocks[d].add(c)

from collections import deque
areas = {i:set() for i in range(1, N+1)}
for i in range(1, N+1):
    q = deque([i])
    while q:
        p = q.pop()
        for f in friends[p]:
            if f not in areas[i] and f != i:
                q.appendleft(f)
                areas[i].add(f)

ans = []
for i in range(1, N+1):
    ans.append(len(areas[i] - friends[i] - blocks[i]))
print(*ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
G = UnionFind(N)

friends = {i:0 for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    friends[a-1] += 1
    friends[b-1] += 1
    G.union(a-1, b-1)

# ブロック関係にあったら友達と考える
for i in range(K):
    c, d = map(int, input().split())
    if G.same(c-1, d-1):
        friends[c-1] += 1
        friends[d-1] += 1

for i in range(N):
    print(G.size(i) - friends[i] - 1, end=' ')
### BUGGY CODE ###

da  = int(input())

k = list(input())
p = [0]*da
for i in range(da):
  for j in range(da):
    if k[i] == "W" and j < i:
      p[j] += 1
    elif k[i] == "E" and j > i:
      p[j] += 1
      
print(da - max(p)-1)

### FIXED CODE ###

da  = int(input())

k = list(input())
p = [0]*da
for i in range(da):
  if k[i] == "E" and i < da -1:
    p[i+1] += 1
  elif k[i] == "W":
    p[0] += 1
    p[i] -= 1

for i in range(1,da):
  p[i] += p[i-1]

k = max(p)
if max(p) != p[0] or max(p) != p[da-1]:
  k += 1
print(da - k)
### BUGGY CODE ###

import collections

def ConZ(i):
    z_num = i+int(i*(i-1)/2)
    return z_num
def ConN(i):
    n_num = int(i*(i-1)/2)
    return n_num

S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = [0]*2019
modcount = []
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    keta*=10
#print(mod[0])
x += ConZ(mod[0])
del mod[0]
c = collections.Counter(mod)
#print(mod)
modcount = list(c.items())
#print(modcount)
for j in range(len(modcount)):
    if modcount[j][0]>=2:
        x+=ConN(modcount[j][0])*modcount[j][1]
print(x)

### FIXED CODE ###

from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))
### BUGGY CODE ###


h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue

        for k in range(h):
            for l in range(w):
                if s[k][l] == '#' or i == k and j == l:
                    continue
                start = (i, j)
                goal = (k, l)
                d = [[1<<10 for x in range(w)] for y in range(h)]

                stack = []
                stack.append((start[0], start[1]))
                d[start[0]][start[1]] = 0
                while stack:
                    y, x = stack.pop()
                    if y == goal[0] and x == goal[1]:
                        continue
                    if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                        d[y-1][x] = d[y][x] + 1
                        stack.append((y-1, x))
                    if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                        d[y][x+1] = d[y][x] + 1
                        stack.append((y, x+1))
                    if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                        d[y+1][x] = d[y][x] + 1
                        stack.append((y+1, x))
                    if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                        d[y][x-1] = d[y][x] + 1
                        stack.append((y, x-1))
                ans.append(d[goal[0]][goal[1]])
ans.sort()
print(ans[-1])


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[False for x in range(w)] for y in range(h)]

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)
### BUGGY CODE ###

import numpy as np 

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

A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = sum(bottom_bit[bottom_bit==1])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)

### FIXED CODE ###

import numpy as np 

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

A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = np.sum(bottom_bit[bottom_bit>0])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

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

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))

### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

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

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))
### BUGGY CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
d=[10000 for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n):
    d[i]=0
    for j in range(i,n):
        if(i==j):continue
        d[j]=min(abs(i-j),abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)
    for j in range(n):
        ans[d[j]]+=1

for i in range(1,n):
    print(ans[i])

### FIXED CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
d=[10000 for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        m=min(abs(i-j),abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)
        ans[m]+=1

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

import sys
from collections import deque
import numpy as np
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n = I()
    a = np.array(list(IL()),dtype='int64')
    q = I()
    s = deque()
    for rep in range(q):
        b,c = IL()
        a[a==b] = c
        s.append(sum(a))
    for _ in range(q):
        print(s.popleft())
    return

if __name__=='__main__':
    Main()

### FIXED CODE ###

import sys
from collections import deque, Counter
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n = I()
    a = list(IL())
    C = Counter(a)
    m = sum(a)
    q = I()
    s = []
    for rep in range(q):
        b,c = IL()
        if b in C:
            m += (c-b)*C[b]
            C[c] += C[b]
            C[b] = 0
        s.append(m)
    for rep in s:
        print(rep)
    return

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

import numpy as np
n,q= map(int,input().split())
s = list(input())
td = [input().split() for _ in range(q)]
data = {i :[] for i in list(set(s))}
for j,i in enumerate(s):
  data[i].append(j+1)

ans = np.array([0]+[1]*n+[0])

for i,j in td:
  if i in s:
    temp = ans[data[i[0]]].copy()
    ans[data[i[0]]]=0
    if j=='L':
      ans[np.array(data[i[0]])-1]+=temp
    else:
      ans[np.array(data[i[0]])+1]+=temp
print(n-ans[0]-ans[-1])

### FIXED CODE ###

n,q= map(int,input().split())
s = [0]+list(input())+[0]
td = [input().split() for _ in range(q)]
l,r = 0,n+1
for i,j in td[::-1]:
  if s[l+1]==i and j=='L':
    l+=1
  elif s[l]==i and j=='R':
    l-=1
  if s[r-1]==i and j=='R':
    r-=1
  elif s[r]==i and j=='L':
    r+=1
print(max(0,r-l-1))