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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:L//2] :
            i += L//2
            continue
        if ANS[i] : continue
        else: ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

s=input()

answer=0
for n in range(4,len(s)):
  for i in range(len(s)-n+1):
    a=s[i:i+n]
    b=int(a)
    if b%2019==0:
      answer=answer+1
        
print(answer)

### FIXED CODE ###

s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
b=0.1
for i in range(len(s)):
  b=int(b*10)
  b%=2019
  a+=s[i]*b
  a%=2019
  l[a]+=1

answer=0
for i in range(2019):
  answer+=l[i]*(l[i]-1)//2
  
print(answer)
### BUGGY CODE ###

import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
while N:
    if len(data) > 1:
        xl, hl = data[0]
        xr, hr = data[-1]
        if hl < hr:
            h = hr
            t = xr - D
        else:
            h = hl
            t = xl + D
    else:
        t, h = data[0]
    
    # 大きい方を殺す
    attack = math.floor(h / A)
    c += attack

    # 爆破させる場所
    # t = hl + D or hr - D    
    # abs(t - x) <= D が攻撃を受ける

    use = []
    for i in range(len(data)):
        x, h = data[i]
        if abs(t - x) <= D:
            h -= A * attack
            if h <= 0:
                N -= 1
            else:
                use.append((x, h))
        else:
            use.append((x,h))
    data = use[:]


print(c)

### FIXED CODE ###

import math
from collections import deque

N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, math.ceil(h/A)))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 # 有効なダメージ合計
for i in range(N):
    x, h = data[i]

    # 爆破範囲が届いていなければ削除していく
    while damage_que and x > damage_que[0][0]:
        _, a = damage_que.popleft()
        attack -= a
    
    # 有効な過去の爆破攻撃を受ける
    remain = max(h - attack, 0)
    # 0になるまで爆破    
    attack += remain
    c += remain

    # 爆破回数追加    
    damage_que.append([x+2*D, remain])

print(c)
### BUGGY CODE ###

def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    nxt = cur.copy()

    for weight, value in weight_value:
        for i in range(1, weight):
            nxt[i] = cur[i]
        for i in range(weight, w + 1):
            nxt[i] = max(cur[i], cur[i - weight] + value)
        cur, nxt = nxt, cur
    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())


### FIXED CODE ###

def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    nxt = [0] * (w + 1)

    for weight, value in weight_value:
        for i in range(1, weight):
            nxt[i] = cur[i]
        for i in range(weight, w + 1):
            nxt[i] = max(cur[i], cur[i - weight] + value)
        cur, nxt = nxt, cur
    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())
### BUGGY CODE ###

# C 
import numpy as np

# n = 127
n = int(input())

max_n = 100000
memo = np.full(max_n,999999,dtype=np.int64)
memo[0] = 0

nl6 = [1, 6, 36, 216, 1296, 7776, 46656]
nl9 = [1, 9, 81, 729, 6561, 59049]


for i in range(1,n+1):
    memo[i] = memo[i-1]+1
    for i6 in nl6:
        if(i-i6 >= 0):
            memo[i] = min(memo[i], memo[i-i6]+1)
        
    for i9 in nl9:
        if(i-i9 >= 0):
            memo[i] = min(memo[i], memo[i-i9]+1)
            
print(memo[n])

### FIXED CODE ###

# C 
# import numpy as np

# n = 127
n = int(input())

max_n = 100000
# memo = np.full(max_n,999999,dtype=np.int32)
memo = [999999]*(max_n+1)
memo[0] = 0

# nl6 = [1, 6, 36, 216, 1296, 7776, 46656]
# nl9 = [1, 9, 81, 729, 6561, 59049]


for i in range(1,n+1):
    memo[i] = memo[i-1]+1
    k = 6
    while i-k >= 0:
        memo[i] = min(memo[i], memo[i-k]+1)
        k *= 6
    k = 9
    while i-k >= 0:
        memo[i] = min(memo[i], memo[i-k]+1)
        k *= 9
        
print(memo[n])
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=4096
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

n=int(input())

#初期化
#コイン1円
dp=[i for i in range(n+1)]

#コイン6円
i=1
while 6**i<=n:
    dp[6**i]=1
    i+=1
#コイン6円
i=1
while 9**i<=n:
    dp[9**i]=1
    i+=1

for i in range(1,n+1):
    for j in range(i):
        dp[i]=min(dp[i],dp[j]+dp[i-j])
    #if i%1000==0:
        #print(i)
print(dp[-1])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


n=int(input())

#dpで解く再帰

memo=[-1]*(n+1)
memo[0]=0

def fuck(x):
    #print(x)
    if memo[x]!=-1:
        return memo[x]
    else:
        tmp=10**9
        #6
        i=1
        while 6**i<=x:
            tmp=min(fuck(x-6**i),tmp)
            i+=1
        #9
        i=1
        while 9**i<=x:
            tmp=min(fuck(x-9**i),tmp)
            i+=1
        #1
        tmp=min(tmp,fuck(x-1))
        memo[x]=tmp+1
        #print(x,tmp+1,memo)
        return tmp+1
fuck(n)
#print(memo)
print(memo[-1])
### BUGGY CODE ###

a, b, n = map(int, input().split())
 
tmp = 0
for x in (range(1, b+1) if b<=n else range(1, n+1, n-1)):
#for x in range(1, n+1):
    calc = a*x//b - a*(x//b)
    if calc > tmp:
        tmp = calc
 
print(tmp)

### FIXED CODE ###

a, b, n = map(int, input().split())
 
tmp = 0
for x in (range(1, b+1, b-2) if b<=n else range(1, n+1, n-1)):
#for x in range(1, n+1):
    calc = a*x//b - a*(x//b)
    if calc > tmp:
        tmp = calc
 
print(tmp)
### BUGGY CODE ###

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

roads = []
for i in range(m):
    x,y = map(int, input().split())
    roads.append([x-1,y-1])

bestcount = 0

for i in range(n):
    best = 1 # 良い展望台なら1
    for j in range(m):
        if (roads[j][0] == i):
            a = roads[j][0]
            b = roads[j][1]
            if (height[a] <= height[b]):
                best = 0
        if (roads[j][1] == i):
            a = roads[j][1]
            b = roads[j][0]
            if (height[a] <= height[b]):
                best = 0
    if(best == 1):
        bestcount += 1

print(str(bestcount))

### FIXED CODE ###

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

roads = [[] for i in range(n)]
for i in range(m):
    x,y = map(int, input().split())
    roads[x-1].append(y-1)
    roads[y-1].append(x-1)

bestcount = 0

for i in range(n):
    best = 1 # 良い展望台なら1
    for j in roads[i]:
        if (height[j] >= height[i]):
            best = 0
            break
    if(best == 1):
        bestcount += 1

print(str(bestcount))
### BUGGY CODE ###

mod=10**9+7
n=int(raw_input())
l=len(raw_input())
dp=[[0]*(n+2) for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=dp[i-1][1]*2+dp[i-1][0]
        else:dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]*2
print dp[n][l]%mod


### FIXED CODE ###

mod=1000000007
n=int(raw_input())
l=len(raw_input())
dp=[[0 for i in range(n+2)] for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]
### BUGGY CODE ###

def calc_E(prob):

    E = sum([i for i in range(1, prob+1)]) / prob
    return E

def main(N, K, list_p):
    
    list_E = list(map(calc_E, list_p))
    max_E  = sum(list_E[0:K])
    prev_E = sum(list_E[0:K])

    for i in range(1, N-K+1):
        tmpE   = prev_E - list_E[i-1] + list_E[i-1+K]
        max_E  = max(max_E, tmpE)
        prev_E = tmpE

    return max_E
        


if __name__ == "__main__":

    [N, K] = list(map(int, input().split(' ')))
    list_p = list(map(int, input().split(' ')))

    answer = main(N, K, list_p)
    print(answer)

### FIXED CODE ###

def calc_E(prob):

    E = (prob + 1) / 2
    return E

def main(N, K, list_p):
    
    list_E = list(map(calc_E, list_p))
    max_E  = sum(list_E[0:K])
    prev_E = sum(list_E[0:K])

    for i in range(1, N-K+1):
        tmpE   = prev_E - list_E[i-1] + list_E[i-1+K]
        max_E  = max(max_E, tmpE)
        prev_E = tmpE

    return max_E
        


if __name__ == "__main__":

    [N, K] = list(map(int, input().split(' ')))
    list_p = list(map(int, input().split(' ')))

    answer = main(N, K, list_p)
    print(answer)
### BUGGY CODE ###

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

for i in range(N):
    A_sum = A_sum * A[i]
    
    if A_sum == 0:
        break
    

if A_sum > 1e18:
        print(-1)

else:
    print(A_sum)

### FIXED CODE ###

import sys

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

if min(A) == 0:
    print(0)
    sys.exit()

else:
    for i in range(N):
        A_sum = A_sum * A[i]
        
        if A_sum > 1e18:
            print(-1)
            sys.exit()


print(A_sum)
### BUGGY CODE ###

n=int(input())
list=[""]*n
number=0
already=[]
bad=0
for i in range(n):
  list[i]=str(input())
for i in range(n):
  for j in range(len(already)):
    if list[i]==already[j]:
      bad=1
      break
  if bad==0:
    number+=1
    already.append(list[i])
  bad=0
print(number)

### FIXED CODE ###

n=int(input())
list=[]
for i in range(n):
  list.append(input())
print(len(set(list)))
### BUGGY CODE ###

A,B,K=map(int,input().split())
S=(set(range(A,A+K))|set(range(B-(K-1),B+1)))&set(range(A,B+1))
S=list(S)
S.sort()

for x in S:
    print(x)


### FIXED CODE ###

A,B,K=map(int,input().split())
S=(set(range(A,A+K))|set(range(B-(K-1),B+1)))
S=list(S)
S.sort()

for x in S:
    if A<=x<=B:
        print(x)
### BUGGY CODE ###

from collections import deque
def inputs(): return [int(x) for x in input().split()]
s = deque(input())
q = int(input())
for i in range(q):
    q1 = input()
    if len(q1)==1:
        s = deque(reversed(s))
    else:
        l,f,c = q1.split()
        if int(f)==1:
            s.appendleft(c)
        else:
            s.append(c)
print("".join(list(s)))


### FIXED CODE ###

from collections import deque
def inputs(): return [int(x) for x in input().split()]
s = deque(input())
q = int(input())
flag = 1
for i in range(q):
    q1 = input()
    if len(q1)==1:
      flag *=-1 
    else:
        l,f,c = q1.split()
        if flag ==1:
            if int(f)==1:
                s.appendleft(c)
            else:
                s.append(c)
        elif flag==-1:
            if int(f)==1:
                s.append(c)
            else:
                s.appendleft(c)
if flag==1:
    print("".join(list(s)))
else:
    s = list(s)
    s = s[::-1]
    print("".join(list(s)))
### BUGGY CODE ###

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

from collections import Counter
a = Counter(A)
x = 0

for _ in range(q):
    b, c = map(int, input().split())
    a[c] += a[b]
    a[b] = 0

    s = 0
    for i,v in a.items():
        if v != 0:
            s += i*v
    print(s)

### FIXED CODE ###

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

from collections import Counter
arr = Counter(A)
ans = sum([i*arr[i] for i in arr])
 
for i in range(q):
    b,c = list(map(int,input().split()))
    ans += (c-b)*arr[b]
    arr[c],arr[b] = arr[c]+arr[b],0
    print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for i in range(N):
    a = i//n
    b = i%n
    dist[i] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N
from collections import deque
for I,pi in enumerate(p):
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = deque([pi])
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        d = dist[v]
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if nv < 0 or nv >= N: continue
            
            if dist[nv] > d + iru[v]:
                q.append(nv)
                dist[nv] = d + iru[v]
        
                    
    #print(dist)        

print(ans)









### FIXED CODE ###

# coding: utf-8
# Your code here!

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

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for a in range(n):
    for b in range(n):
        dist[a*n+b] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N

for pi in p:
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = [pi]
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                q.append(nv)
                dist[nv] = dist[v] + iru[v]
        
                    
    #print(dist)        

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

def main():
    import numpy as np
    n = int(input())
    a = np.array(list(map(int, input().split())), dtype=np.int64)
    l1 = [0]*61
    mod = 10**9+7
    #n = 300000
    #a = np.array([2**60-i for i in range(n)])
    for cnt in range(61):
        b = a % 2
        l1[cnt] = sum(b)
        a = a // 2
    l0 = [n-i for i in l1]
    ans = 0
    for i in range(len(l1)):
        ans = (ans+l0[i]*l1[i]*pow(2, i, mod)) % mod
    print(ans)


main()


### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    l1=[0]*61
    for i in a:
        j=list(reversed(bin(i)[2:]))
        for k in range(len(j)):
            if j[k]=="1":
                l1[k]+=1
    l0=[n-i for i in l1]
    ans=0
    mod=10**9+7
    for i in range(len(l1)):
        ans=(ans+l0[i]*l1[i]*pow(2,i,mod))%mod
    print(ans)
main()
### BUGGY CODE ###

n = int(input())
M = [i for i in range(n)]
print(sum(M))

### FIXED CODE ###

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

N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * pow(factorial[x], mod-2, mod) % mod


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[k][n] += f(n, k, x) * dp[k - 1][n - k * x] % mod

print(dp[N][N])


### FIXED CODE ###

N, A, B, C, D = map(int, raw_input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in xrange(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


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

for k in xrange(A, B + 1):  # k人からなるグループをこれから作りますよ
    for n in range(1, N + 1)[::-1]:  # すでにn人は使っちゃってますよ
        X = xrange(C, D + 1)
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[n] += f(n, k, x) * dp[n - k * x] % mod

print(dp[N] % mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

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

import re
X = raw_input()
iter = 100000
#pat = re.compile('(ST)')
for i in xrange(iter):
    X =	X.replace('ST','')
    if len(X) == 0:
        break
print len(X)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    x = S()
    s_cnt = 0
    removed = 0
    for c in x:
        if c == 'S':
            s_cnt += 1
        if c == 'T':
            if s_cnt > 0:
                s_cnt -= 1
                removed += 2
    print(len(x) - removed)
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in set(a):
    temp = a.count(i)
    if temp > i:
        ans.append(temp - i)
    elif temp < i:
        ans.append(temp)
print(sum(ans))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ans = 0
for i, j in c.items():
    if i > j:
        ans += j
    elif i < j:
        ans += (j - i)
print(ans)
### BUGGY CODE ###

n = int(input())
alist = list(map(int, input().split()))
result = 1
for a in alist:
  result *= a
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

def solve(alist):
    if 0 in alist:
        return 0
    result = 1
    for a in alist:
        result *= a
        if result > 10**18:
            return -1
    return result

n = input()
alist = list(map(int, input().split()))
print(solve(alist))
### BUGGY CODE ###

# - coding : utf-8 -*-

import sys

if __name__ == '__main__':
    n, m = map(int, raw_input().split())
    cities = []
    city_lst = {}
    for i in range(0, m):
        p, y = map(int, raw_input().split())
        cities.append((p, y))
        if not p in city_lst:
            city_lst[p] = [y]
        else:
            city_lst[p].append(y)
    for key in city_lst.keys():
        city_lst[key].sort()
    for city in cities:
        print str('%06d' % city[0]) + str('%06d' % (int(city_lst[city[0]].index(city[1]) + 1)))
        sys.stdout.flush()

### FIXED CODE ###

# - coding : utf-8 -*-

if __name__ == '__main__':
    n, m = map(int, raw_input().split())
    cities = []
    for i in range(0, m):
        p, y = map(int, raw_input().split())
        cities.append((y, p, i))
    cities.sort()

    city_codes = [0] * (n + 1)
    postal_codes = [""] * m
    for j in range(0, m):
        y, p, i = cities[j]
        city_codes[p] += 1
        postal_codes[i] = "%06d%06d"%(p, city_codes[p])
    for postal_code in postal_codes:
        print postal_code
### BUGGY CODE ###

import math

n = int(input())

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


listi = [a[i] +i+1 for i in range(n)]
listj = [i+1 -a[i] for i in range(n)]

c = 0
for i in range(n):
    for j in range(i+1,n):
        if listi[i] == listj[j]:
            c += 1
print(c)

### FIXED CODE ###

import collections

n = int(input())

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


l = [a[i] +i+1 for i in range(n)]
r = [i+1 -a[i] for i in range(n)]

L = collections.Counter(l)
R = collections.Counter(r)

c = 0

for i in L.keys():
    c += L.get(i, 0) * R.get(i, 0)

print(c)