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

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    for i in range(N):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    break
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        break
            else:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=1)
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    return True
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        return True
        else:
            return True
        return False
    
    res=nibutan(-1,N)
    print(N-1-res)
    


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

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

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0
    
for i in range(N):
    lst[A[i]] += 1

llst = dict(lst) # llst は、valueが1のものを消したリスト
for i in lst:
    if lst[i] == 1:
        llst.pop(i)

c = dict(lst) # c は keyの値である場合の組み合わせの数。
              # c = dict(lst)で異なるオブジェクトとして等価なcを定義
              # c = lst だと、同一のオブジェクトとなってしまう？

for i in lst:
    c[i] = 0
    tmp_lst = dict(llst)
    if lst[i] != 1:
        tmp_lst[i] -= 1
    for j in tmp_lst:
        c[i] += tmp_lst[j]*(tmp_lst[j]-1)//2
        
for i in range(N):
    print(c[A[i]])

### FIXED CODE ###

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

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0
    
for i in range(N):
    lst[A[i]] += 1

llst = dict(lst) # llst は、valueが1のものを消したリスト
for i in lst:
    if lst[i] == 1:
        llst.pop(i)

c = dict(lst) # c は keyの値である場合の組み合わせの数。
              # c = dict(lst)で異なるオブジェクトとして等価なcを定義
              # c = lst だと、同一のオブジェクトとなってしまう？
c_all = 0
for j in llst:
    c_all += llst[j]*(llst[j]-1)//2

# print('c_all:{}'.format(c_all))
for i in lst:
#     print('i:{}'.format(i))
#     print('lst[i]:{}'.format(lst[i]))
    c[i] = c_all
    c[i] = c[i] - lst[i]*(lst[i]-1)//2 + (lst[i]-1)*(lst[i]-2)//2
        
for i in range(N):
    print(c[A[i]])
### BUGGY CODE ###

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

for i in range(n):
  if all([p[i]<=p[j] for j in range(i)]):
    cnt+=1
    
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
min=p[0]

for i in range(n):
  if p[i]<=min:
    cnt+=1
    min=p[i]
    
print(cnt)
### BUGGY CODE ###

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A
    
if __name__ == '__main__':
    N = int(input())
    A = InputToInt()

    for i in range(N):
        s = 0
        for j in range(0,N-2,2):
            s += A[(i+j)%N] - A[(i+j+1)%N]
        print(s + A[(i-1)%N], end=" ")


### FIXED CODE ###

import numpy as np

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A
    
if __name__ == '__main__':
    N = int(input())
    A = InputToInt()

    s = np.zeros(N)
    for j in range(0,N-2,2):
        s[0] += A[j] - A[j+1]
    s[0] += A[N-1]
    s[N-1] = (A[N-1] - s[0]/2)*2

    for i in range(2,N):
        s[N-i] = (A[N-i] - s[N-i+1]/2)*2
    for i in range(N):
        print(int(s[i]), end=" ")
### BUGGY CODE ###

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7

def C(n,m):
    arr = np.zeros((n+1,m+1),int)
    arr[0][0] = 1 
    i = 1 
    while(i < n+1):
        arr[i][0] = 1 
        j = 1 
        while(j< i+1):
            arr[i][j] = (arr[i-1][j] + arr[i-1][j-1]) % MAX 
            j+=1 
        i+=1 
    return(arr)  

n,k = input().split()
n,k = int(n),int(k) 

arr = C(2000,2000)

for i in range(k):
    ans = ( arr[n-k+1][i+1] * arr[k-1][i] ) % MAX 
    print (ans)



### FIXED CODE ###

#atcoder_RedAndBlueBalls

import numpy as np 

MAX = pow(10,9)+7

def fact(n):
    ls = [1] 
    for i in range(1,n+1):
        ls.append(ls[i-1]*i) 
    return(ls) 

n,k = input().split()
n,k = int(n),int(k) 

ls = fact(2000)

def C(n,m):
    return ((ls[n]//(ls[m]*ls[n-m])) % MAX)

for i in range(k):
    ans = ( C(n-k+1,i+1) * C(k-1,i) ) % MAX 
    print (ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import functools


@functools.lru_cache(1024)
def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3(i) and is_prime3((i + 1) // 2):
            ans += 1
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])
### BUGGY CODE ###

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

a.sort()

divisors = {}

divisors[a[0]] = 1

for i in range(1,n):
  div_flag = False
  for div in divisors.keys():
    if a[i]%div == 0:
      div_flag = True
      if div%a[i] == 0:
        divisors[div] = 0
      break
  if div_flag:
    continue
  else:
    divisors[a[i]] = 1

ans = 0
for key in divisors.keys():
  ans += divisors[key]
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+1

is_divided = [0]*MAX 
is_appeared = [0]*MAX

for i in range(n):
  if not is_divided[a[i]]:
    if not is_appeared[a[i]]:
      is_appeared[a[i]] = 1
      k = a[i]*2
      while k < MAX:
        is_divided[k] = 1
        k += a[i]
    else:
      is_divided[a[i]] = 1
      
ans = 0      
for i in range(n):
  if not is_divided[a[i]]:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(input())
    h = list(map(int, input().split()))
    ans = 0
    while sum(h) > 0:
        for i in range(N):
            for j in reversed(range(1, N - i + 1)):
                if min(h[i:i + j]) > 0:
                    for k in range(i, i + j):
                        h[k] -= 1
                    ans += 1
                    break
            else:
                continue
            break
    print(ans)

main()


### FIXED CODE ###

import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def f(arr):
    m = min(arr)
    for i in range(len(arr)):
        arr[i] -= m
    buf = []
    ret = m
    for i in arr:
        if i == 0:
            if len(buf) > 0:
                ret += f(buf)
                buf = []
        else:
            buf.append(i)
    if len(buf) > 0:
        ret += f(buf)
    return ret

def main():
    N = int(input())
    h = list(map(int, input().split()))
    print(f(h))

main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list()
for i in range(M):
  A.append(int(input()))
ans = [0] * (N+1)
for i in range(N+1):
  if(i not in A):
    if(i == 0 or i == 1):
      ans[i] = 1
    else:
      ans[i] = (ans[i-1]+ans[i-2])%1000000007
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10**9 + 7
ans = [0] * (N+1)
ans[0] = 1
ans[1] = 1 if 1 not in A else 0
for i in range(2, N+1):
  ans[i] = (ans[i-1]+ans[i-2])%mod if i not in A else 0
print(ans[N])
### BUGGY CODE ###

from operator import mul
from functools import reduce
n, k = map(int, input().split())
A = list(map(int, input().split()))
before = reduce(mul, A[:k])

for i in range(1, n-k+1):
    tmp = reduce(mul, A[i:k+i])
    if tmp > before:
        print("Yes")
    else:
        print("No")
    before = tmp

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
before = sum(A[:k])

for i in range(n-k):
    tmp = before + A[i+k] - A[i]
    if tmp > before:
        print("Yes")
    else:
        print("No")
    before = tmp
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
  #print(i, "------------------------------")
  k = A[i]
  for j in range(i + k, N):
    #print(j - i, A[i] + A[j])
    if j - i == A[i] + A[j]:
      #print(i, j, A[i], A[j])
      ans += 1
else:
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = {}
R = {}
ans = 0
for i in range(N):
  t = i + 1 + A[i]
  if t in L:
    L[t] += 1
  else:
    L[t] = 1
  t = i + 1 - A[i]
  if t > 0:
    if t in R:
      R[t] += 1
    else:
      R[t] = 1
for i in R:
  if i in L:
    ans += R[i] * L[i]
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
count_dict = collections.Counter(A)
d = []
for k,v in count_dict.items():
	d.append(k)

ans = 0
for i in range(max(d)+1):
	count = 0
	for j in range(N):
		if A[j] == i or A[j]+1 == i or A[j]-1 == i:
			count += 1
		ans = max(ans,count)
print(ans)

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    max_a = max(a)
    count = [0 for _ in range(max_a+1)]
    c = collections.Counter(a)
    c = list(c.items())

    if len(c) == 1:
        print(c[0][1])

    elif len(c) == 2:
        if abs(c[0][0]-c[1][0]) <= 2:
            print(c[0][1]+c[1][1])
        else:
            print(max(c[0][1],c[1][1]))

    else:
        for i in range(len(c)):
            count[c[i][0]] = c[i][1]

        sum_list = [0 for _ in range(len(count)-2)]
        for i in range(len(count)-2):
            sum_list[i] = count[i]+count[i+1]+count[i+2]
        print(max(sum_list))

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

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


min_ct = 1000000000
for i in range(N):
    ct = 0
    num_W = S[0:i+1].count("W")
    num_E = S[i:N].count("E")
    ct += num_W + num_E
    if min_ct > ct:
        min_ct = ct


print(min_ct-1)


### FIXED CODE ###

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

num_W = 0
num_E = 0
for i in range(1,N):
    if S[i] == "E":
        num_E += 1
min_ct = num_W + num_E

for i in range(1,N):
    if S[i-1] == "W":
        num_W += 1
    if S[i] == "E":
        num_E -= 1
    ct = num_W + num_E
    if min_ct > ct:
        min_ct = ct


print(min_ct)
### BUGGY CODE ###


def section_sum(a, b):
    return acc[b] - acc[a]


def minimize(s2):
    lsum = float("inf")
    for s1 in range(1, s2):
        if abs(section_sum(0, s1) - section_sum(s1, s2)) < lsum:
            q = section_sum(0, s1)
            r = section_sum(s1, s2)
            lsum = abs(q - r)
        else:
            break

    rsum = float("inf")
    for s3 in range(s2, len(a)):
        if abs(section_sum(s2, s3) - section_sum(s3, len(a))) < rsum:
            s = section_sum(s2, s3)
            t = section_sum(s3, len(a))
            rsum = abs(s - t)
        else:
            break

    cut = [q, r, s, t]
    return abs(min(cut) - max(cut))


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

acc = [0]
for x in a:
    acc.append(acc[-1] + x)


ans = float("inf")
for s2 in range(2, len(a) - 1):
    ans = min(ans, minimize(s2))

print(ans)


### FIXED CODE ###


def section_sum(a, b):
    return acc[b] - acc[a]


def minimize(s1, s2, s3):
    lsum = float("inf")
    for i in range(s1, s2):
        if abs(section_sum(0, i) - section_sum(i, s2)) < lsum:
            q = section_sum(0, i)
            r = section_sum(i, s2)
            s1 = i
            lsum = abs(q - r)
        else:
            break

    rsum = float("inf")
    for i in range(s3, len(a)):
        if abs(section_sum(s2, i) - section_sum(i, len(a))) < rsum:
            s = section_sum(s2, i)
            t = section_sum(i, len(a))
            s3 = i
            rsum = abs(s - t)
        else:
            break

    cut = [q, r, s, t]
    return abs(min(cut) - max(cut)), s1, s2, s3


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

acc = [0]
for x in a:
    acc.append(acc[-1] + x)

s1, s2, s3 = 1, 2, 3
ans = float("inf")
for s2 in range(2, len(a) - 1):
    x, s1, s2, s3 = minimize(s1, s2, s3)
    ans = min(ans, x)

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

import sys
s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()

S = len(s)
T = len(t)

dp = [[0 for _ in range(T+1)] for _ in range(S+1)]


for i in range(S):
    for j in range(T):
        if s[i] ==t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
'''
for i in rage(S+1):
    print(dp[i])
'''

L =[]
while S>0 and T>0:
    if dp[S][T] != dp[S-1][T-1]+1:
        if dp[S][T] !=dp[S-1][T]:
            T-=1
        else:
            S-=1
    else:
        L.append(s[S-1])
        S-=1
        T-=1
print(''.join(L[::-1]))

### FIXED CODE ###

import sys
s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()

sn = len(s)
tn = len(t)

dp =[[0 for _ in range(tn+1)] for _ in range(sn+1)]

for i in range(sn):
    for j in range(tn):
        if s[i]==t[j]:
            dp[i+1][j+1] =dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
#print(dp)

L =[]
while sn>0 and tn>0:
    if dp[sn][tn] == dp[sn-1][tn]: #縦優先
        sn-=1
    elif dp[sn][tn] == dp[sn][tn-1]:
        tn-=1
    elif dp[sn][tn] == dp[sn-1][tn-1]+1:
        L.append(s[sn-1])
        sn-=1
        tn-=1
        
print(''.join(L[::-1]))
### BUGGY CODE ###

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

def BFS(H, W, L, start):
	dist = [[INF for i in range(W)] for j in range(H)]
	sy, sx = start
	dist[sy][sx] = 0
	Q = queue.Queue()
	Q.put([sy, sx])
	while not Q.empty():
		y, x = Q.get()
		if y - 1 >= 0:
			if L[y - 1][x] == "." and dist[y - 1][x] > dist[y][x] + 1:
				dist[y - 1][x] = dist[y][x] + 1
				Q.put([y - 1, x])
		if y + 1 <= H - 1:
			if L[y + 1][x] == "." and dist[y + 1][x] > dist[y][x] + 1:
				dist[y + 1][x] = dist[y][x] + 1
				Q.put([y + 1, x])
		if x - 1 >= 0:
			if L[y][x - 1] == "." and dist[y][x - 1] > dist[y][x] + 1:
				dist[y][x - 1] = dist[y][x] + 1
				Q.put([y, x - 1])
		if x + 1 <= W - 1:
			if L[y][x + 1] == "." and dist[y][x + 1] > dist[y][x] + 1:
				dist[y][x + 1] = dist[y][x] + 1
				Q.put([y, x + 1])

	return dist

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)
	SG = []
	for i in range(H):
		for j in range(W):
			if L[i][j] == ".":
				SG.append([i, j])

	N = len(SG)
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			start = [SG[i][0] , SG[i][1]]
			goal = [SG[j][0] , SG[j][1]]
			BF = BFS(H, W, L, start)
			val = BF[goal[0]][goal[1]]
			ans = max(ans, val)
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

#ライブラリインポート
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

def BFS(H, W, L, start):
	dist = [[INF for i in range(W)] for j in range(H)]
	sy, sx = start
	dist[sy][sx] = 0
	Q = queue.Queue()
	Q.put([sy, sx])
	while not Q.empty():
		y, x = Q.get()
		if y - 1 >= 0:
			if L[y - 1][x] == "." and dist[y - 1][x] > dist[y][x] + 1:
				dist[y - 1][x] = dist[y][x] + 1
				Q.put([y - 1, x])
		if y + 1 <= H - 1:
			if L[y + 1][x] == "." and dist[y + 1][x] > dist[y][x] + 1:
				dist[y + 1][x] = dist[y][x] + 1
				Q.put([y + 1, x])
		if x - 1 >= 0:
			if L[y][x - 1] == "." and dist[y][x - 1] > dist[y][x] + 1:
				dist[y][x - 1] = dist[y][x] + 1
				Q.put([y, x - 1])
		if x + 1 <= W - 1:
			if L[y][x + 1] == "." and dist[y][x + 1] > dist[y][x] + 1:
				dist[y][x + 1] = dist[y][x] + 1
				Q.put([y, x + 1])

	return dist

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	ans = 0
	for i in range(H):
		for j in range(W):
			if L[i][j] == ".":
				BF = BFS(H, W, L, [i, j])
				for p in range(H):
					for q in range(W):
						if BF[p][q] != INF:
							ans = max(ans, BF[p][q])

	print(ans)


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

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    from collections import deque
    min_cost = float('inf')

    que = deque()
    que.append((0, 0, set(range(1, v))))
    while que:
        cost, last, vs = que.pop()
        if min_cost < cost:
            continue
        if vs:
            que.extend((cost + g[last][v], v, vs - {v}) for v in vs)
        elif min_cost > cost + g[last][0]:
            min_cost = cost + g[last][0]

    print(-1 if isinf(min_cost) else min_cost)

main()

### FIXED CODE ###

# http://www.geocities.jp/m_hiroi/light/pyalgo65.html

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def tsp(p, v):
    if (1 << point_size) - 1 == v:
        return distance_table[p][0]
    else:
        return min(distance_table[p][x] + tsp(x, v | (1 << x)) for x in range(point_size) if not (v & (1 << x)))

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = d
ans = tsp(0,1)
print(-1 if isinf(ans) else ans)
### BUGGY CODE ###

from collections import deque
s = list(input())
ans = 0
k = deque()
for i in range(len(s) + 1):
    l, r = i - 1, i
    while l >= 0:
        if s[l] != "<":
            break
        l -= 1
    while r < len(s):
        if s[r] != ">":
            break
        r += 1
    ans += max(i - l - 1, r - i)
print(ans)

### FIXED CODE ###

s = list(input())
data = [0] * (len(s) + 1)
for i in range(len(s)):
    if s[i] == "<":
        data[i + 1] = data[i] + 1

for i in range(len(s) - 1, -1, -1):
    if s[i] == ">":
        data[i] = max(data[i], data[i + 1] + 1) 
print(sum(data))
### BUGGY CODE ###

S = input()
n = len(S)
# print(n)
M = 2019
# A = [0]
Y = [0]*M
Y[0] = 1
for i in range(1,n+1):
    Y[int(S[-i:])%2019] += 1
    # A.append(int(S[-i:])%2019)
# print(A)
# print(Y)
c = 0
for y in Y:
    if y >= 2:
        c += y*(y-1)//2
print(c)

### FIXED CODE ###

import time

p0 = time.time()
S = input()
n = len(S)
Y = {0:1}
# print(Y)
Y[0] = 1
A = [0]
pk = 0
for i in range(1,n+1):
    # print(S[-i])
    k = (int(S[-i])*pow(10,i-1,2019)+pk)%2019
    A.append(k)
    if k not in Y:
        Y[k] = 1
    else:
        Y[k] += 1
    pk = k

# print(A)
# print(Y)
# print(time.time()-p0)
c = 0
for y in Y:
    d = Y[y]
    c += d*(d-1)//2
print(c)
### BUGGY CODE ###

def gcd(a,b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
		
def gcd_t(a,b,c):
	return gcd(gcd(a, b), c)
	
K = int(input())
result = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for k in range(1, K + 1):
			result += gcd_t(i, j, k)

print(result)

### FIXED CODE ###


from math import gcd

K = int(input())
result = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for k in range(1, K + 1):
			result += gcd(gcd(i, j), k)

print(result)
### BUGGY CODE ###

S = list(input())
Q = int(input())
for i in range(Q):
    Query = input()
    T = int(Query[0])
    if T == 1:
        temp = list(S)
        for j in range(len(S)):
            S[j] = temp[-1-j]
    elif T == 2:
        F = int(Query[2])
        C = Query[4]
        if F == 1:
            S.insert(0, C)
        elif F == 2:
            S.append(C)



print(''.join(S))
print('\n')

### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')
### BUGGY CODE ###

N = int(input())
alist = list(map(int, input().split()))
aset = set(alist)
xset = set()
for a in aset:
    xset.add(a - 1)
    xset.add(a)
    xset.add(a + 1)
max_num = 0
for x in xset:    
        num = len([xx for xx in alist if x -1 <= xx <= x + 1])
        max_num = max(max_num, num)
print(max_num)

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
### BUGGY CODE ###

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

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

### FIXED CODE ###

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

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)