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

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1

idx=0
while idx<len(nxt):
    i=nxt[idx]
    idx+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)
### BUGGY CODE ###

import itertools

n = int(input())

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

zzz = list(itertools.combinations(l,3))

cnt = 0

for z in zzz:
    
    a = z[0]
    b = z[1]
    c = z[2]

    if abs(b-c) < a < b+c:
         cnt += 1

print(cnt)


### FIXED CODE ###

import bisect

n = int(input())

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

l.sort()

cnt = 0

for i in range(n):
    for j in range(i):
        cnt += bisect.bisect_left(l,l[i]+l[j]) - (i + 1)

print(cnt)
### BUGGY CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm=1
for s in A:
    lcm=s*lcm//gcd(lcm, s)

ans = np.sum([lcm*pow(s, mod-2, mod) % mod for s in A]) % mod

print(int(ans))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

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

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if (j == 0 and abs(i)==1) or (i==0 and abs(j)==1):
						if c < Cost[h+i][w+j]:
							Cost[h+i][w+j] = c
							deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
					elif c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

s = [list(map(int,input().split())) for i in range(2)]
t = s[0]
N = t[0]
K = t[1]
H = s[1]
if K > N:
    print(0)
elif K < N//2:
    for i in range(K):
        a = max(H)
        H.remove(a)
    print(sum(H))
else:
    m = 0
    for i in range(N - K):
        a = min(H)
        H.remove(a)
        m = m + a
    print(m)

### FIXED CODE ###

s = [list(map(int,input().split())) for i in range(2)]
t = s[0]
N = t[0]
K = t[1]
H = s[1]
if K > N:
    print(0)
else:
    H.sort()
    H[N - K:N]=[]
    print(sum(H))
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
for i in range(N):
    if S[i]=="R":
        r.append(i)
    elif S[i]=="G":
        g.append(i)
    else:
        b.append(i)

t=0
k=0
A=len(r)
B=len(g)
for i in range(A):
    for j in range(B):

        if 2*r[i]-g[j] in b:
            k+=1
        if 2*g[j]-r[i] in b:
            k+=1
        if (r[i]+g[j])/2 in b:
            k+=1


print(A*B*len(b)-k)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

l,r=map(int,input().split())
ans = 2018
for i in range(l,r+1):
    for j in range(l,r+1):
        if i<j:
            ans = min(ans,(i*j)%2019)
            if ans == 0:break
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())
ans = 2018
for i in range(l,r+1):
    for j in range(l,r+1):
        if i<j:
            ans = min(ans,(i*j)%2019)
            if ans == 0:
                print(0)
                exit()
print(ans)
### BUGGY CODE ###

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())

Ch += 1
Cw += 1
Dh += 1
Dw += 1

S = [["#" for _ in range(W + 4)] for _ in range(2)]
for _ in range(H):
    S.append(["#"] * 2 + list(input()) + ["#"] * 2)
S.append(["#" for _ in range(W + 4)])
S.append(["#" for _ in range(W + 4)])

cnt = [[float("inf")] * (W + 4) for _ in range(H + 4)]
cnt[Ch][Cw] = 0

DX = [0, 0, -1, 1]
DY = [-1, 1, 0, 0]

from collections import deque

def serch(Sh, Sw, count):
    q = [(Sh, Sw)]
    done = [(Sh, Sw)]
    while q:
        qq = []
        for h, w in q:
            for dy, dx in zip(DY, DX):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > count:
                    qq.append((nh, nw))
                    done.append((nh, nw))
                    cnt[nh][nw] = count
        q = qq
    
    return done

DONE = serch(Ch, Cw, 0)
ans = 1
while DONE:
    DDONE = []
    for h, w in DONE:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > ans:
                    cnt[nh][nw] = ans
                    DDONE += serch(nh, nw, ans)
    
    ans += 1
    DONE = DDONE

if cnt[Dh][Dw] == float("inf"):
    print(-1)
else:
    print(cnt[Dh][Dw])

### FIXED CODE ###

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())

Ch += 1
Cw += 1
Dh += 1
Dw += 1

S = [["#" for _ in range(W + 4)] for _ in range(2)]
for _ in range(H):
    S.append(["#"] * 2 + list(input()) + ["#"] * 2)
S.append(["#" for _ in range(W + 4)])
S.append(["#" for _ in range(W + 4)])

cnt = [[float("inf")] * (W + 4) for _ in range(H + 4)]
cnt[Ch][Cw] = 0

DX = [0, 0, -1, 1]
DY = [-1, 1, 0, 0]

from collections import deque

def serch(Sh, Sw, count):
    q = [(Sh, Sw)]
    done = [(Sh, Sw)]
    while q:
        qq = []
        for h, w in q:
            for dy, dx in zip(DY, DX):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > count:
                    qq.append((nh, nw))
                    done.append((nh, nw))
                    cnt[nh][nw] = count
        q = qq
    
    return done

DONE = serch(Ch, Cw, 0)
ans = 1
while DONE:
    DDONE = []
    for h, w in DONE:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > ans:
                    cnt[nh][nw] = ans
                    DDONE += serch(nh, nw, ans)
    
    ans += 1
    DONE = DDONE

if cnt[Dh][Dw] == float("inf"):
    print(-1)
else:
    print(cnt[Dh][Dw])
### BUGGY CODE ###

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

if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()
    s = 2
else:
    s = 1

for i in range(s, N, 2):
    if A.count(i) != 2:
        print(0)
        quit()
print(2**(N//2))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()

c = {}
for e in A:
    if e == 0:
        continue
    if e in c.keys():
        c[e] += 1
    else:
        c[e] = 1
if all([x == 2 for x in c.values()]):
    print(2**(N//2)%(10**9+7))
else:
    print(0)
### BUGGY CODE ###

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

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

for i in range(M):
  l,r=map(int,input().split())
  xmat[l][r]+=1
#print(xmat)

for i in range(1,N+1):
  for j in range(1,N+1):
    cmat[i][j]=xmat[i][j]+cmat[i][j-1]
#print(cmat)

for i in range(Q):
  p,q=map(int,input().split())
  ans=0
  for k in range(p,q+1):
    ans+=cmat[k][q]-cmat[k][p-1]
  print(ans)

### FIXED CODE ###

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

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

for i in range(M):
  l,r=map(int,input().split())
  xmat[l][r]+=1
#print(xmat)

for i in range(1,N+1):
  for j in range(1,N+1):
    cmat[i][j]=xmat[i][j]+cmat[i][j-1]
#print(cmat)

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

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]

    prime_list = primes(max(A)+1)

    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

N = int(input())
S = input()
Q = int(input())
L = list(S)
for j in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) -1
        L[i] = c
    else:
        l, r = q[1:]
        l = int(l) - 1
        r = int(r) - 1
        print(len(set(L[l:(r+1)])))

### FIXED CODE ###

class SegmentTree():
    def segfunc(self, x, y):
        return x|y #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, s):
        x = 1<<(ord(s)-97)
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
    

N = int(input())
S = list(input())
for i in range(N):
    S[i] = 1<<(ord(S[i])-97)
Seg = SegmentTree(S)
Q = int(input())
for i in range(Q):
    x, y, z = input().split()
    if int(x) == 1:
        Seg.update(int(y)-1, z)
    else:
        print(popcount(Seg.query(int(y)-1, int(z))))
### BUGGY CODE ###

N = int(input())
info = []
arrive = []
for i in range(N-1):
	info.append(list(map(int,input().split(" "))))


for i in range(N-1):
	C = info[i][0]
	S = info[i][1]
	F = info[i][2]
	next_arrive = []
	for j in arrive:
		if j <= S:
			next_arrive.append(S+C)
		else:
			if j % F == 0:
				next_arrive.append(j+C)
			else:
				cnt = S + F
				while cnt < j:
					cnt += F
				next_arrive.append(cnt+C)

	next_arrive.append(S+C)
	arrive = next_arrive[:]

arrive.append(0)

for ans in arrive:
	print(ans)


### FIXED CODE ###

N = int(input())
info = []
arrive = []
for i in range(N-1):
	info.append(list(map(int,input().split(" "))))


for i in range(N-1):
	C = info[i][0]
	S = info[i][1]
	F = info[i][2]
	next_arrive = []
	for j in arrive:
		if j <= S:
			next_arrive.append(S+C)
		else:
			if j % F == 0:
				next_arrive.append(j+C)
			else:
				cnt = F * ((j // F) + 1)
				next_arrive.append(cnt+C)

	next_arrive.append(S+C)
	arrive = next_arrive[:]

arrive.append(0)

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

n = int(input())
a_list = [int(x) for x in input().split()]
ans = 1
for a in a_list:
    ans *= a
print(ans if ans <= 10 ** 18 else -1)

### FIXED CODE ###

n = int(input())
a_list = sorted([int(x) for x in input().split()], reverse=True)

if a_list[-1] == 0:
    print(0)
    exit()

ans = 1
s = 10 ** 18
for a in a_list:
    ans *= a
    if ans > s:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

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

import math
ans=0
for i in range(n):
    check=True
    for k in range(i):
        if A[k]/2>(A[i]):
            break
        if A[i]%A[k]==0:
            check=False
            break
    if i!=n-1:
        if A[i]==A[i+1]:
            check=False
    if check:
        ans+=1


print(ans)



### FIXED CODE ###

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

box=[True]*(A[-1]+1)

for i in range(len(A)):
    if i<n-1 and A[i]==A[i+1]:
        box[A[i]]=False
    k=2
    while A[i]*k<len(box):
        box[A[i]*k]=False
        k+=1

ans=0
for i in A:
    if box[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            a, b, c = l[i], l[j], l[k]
            if a >= b + c:
                continue
            if b >= c + a:
                continue
            if c >= a + b:
                continue
            ans += 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)
### BUGGY CODE ###


s=input()
n = int(input())

for _ in range(n):
    i = list(input())

    if i[0] == '1': s=s[::-1]

    else:
        if i[2] == '1':  s=i[4] + s
        else: s+=i[4]

print(s)

### FIXED CODE ###

from collections import deque
s=input()
n = int(input())

f=False
q= deque(s)

for _ in range(n):
    i = input()

    if i[0] == '1': f=False if f else True
    else:
        _,a,b =i.split()
        
        if f :
            if a == '1':q.append(b)
            else:q.appendleft(b)
        else:
            if a == '1':q.appendleft(b)
            else:q.append(b)

if f: q.reverse()

for i in q:print(i,end='')
### BUGGY CODE ###

n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)
ans=1
for _ in range(n-1):
    ll=[]
    for i in l:
        if i[1]>=l[0][0]:
            ll.append(i)
    l=ll
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)
### BUGGY CODE ###

I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(int,input().split()))
for i in range(M):
    num = A.index(max(A))
    A[num] = A[num] / 2
ans = 0
for i in range(N):
    ans += int(A[i])
print(ans)

### FIXED CODE ###

import heapq
import math
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(lambda x:-x,map(int,input().split())))
heapq.heapify(A)
for i in range(M):
    num = heapq.heappop(A)
    num = math.ceil(num / 2)
    heapq.heappush(A,num)

print(-sum(A))
### BUGGY CODE ###

s = list(input())
s.reverse()

while len(s):
    if s[:5] == list("maerd"):
        del s[:5]
        continue
    if s[:7] == list("remaerd"):
        del s[:7]
        continue
    if s[:5] == list("esare"):
        del s[:5]
        continue
    if s[:6] == list("resare"):
        del s[:6]
        continue
    break

if s == []:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = list(input())
 
while len(a) >= 5:
    if a[-5:] == list('dream'):
        del a[-5:]
        continue
    if a[-7:] == list('dreamer'):
        del a[-7:]
        continue
    if a[-5:] == list('erase'):
        del a[-5:]
        continue
    if a[-6:] == list('eraser'):
        del a[-6:]
        continue
    break
 
if a == []:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

nq=list(map(int,input().split()))
n=[]
p=[]
t=[]
ans1=[]
ans2=[]
for i in range(nq[0]):
	inp=input().split()
	n.append(int(inp[1]))
	p.append(0)
	t.append(inp[0])

cnt=0
time=0
while n!=p:
	if n[0]==0:
		x=0
		y=0
		x=n[0]
		y=t[0]
		for j in range(len(n)-1):
			n[j]=n[j+1]
			t[j]=t[j+1]
		n[len(n)-1]=x
		t[len(t)-1]=y
	
	else:	
		n[0]=n[0]-nq[1]
		if n[0]<=0:
			time=time+(int(nq[1])*(cnt+1)+int(n[0]))
			cnt=0
			n[0]=0
			x=0
			y=0
			x=n[0]
			y=t[0]
			for j in range(len(n)-1):
				n[j]=n[j+1]
				t[j]=t[j+1]
			n[len(n)-1]=x
			t[len(t)-1]=y
			ans1.append(t[len(t)-1])
			ans2.append(time)
			
			
		else:
			x=0
			y=0
			x=n[0]
			y=t[0]
			for j in range(len(n)-1):
				n[j]=n[j+1]
				t[j]=t[j+1]
			n[len(n)-1]=x
			t[len(t)-1]=y
			cnt+=1
for i in range(nq[0]):
	print(ans1[i],ans2[i])


### FIXED CODE ###

n=[]
t=[]
nq=list(map(int,input().split()))
for i in range(nq[0]):
	inp=input().split()
	n.append(int(inp[1]))
	t.append(inp[0])
cnt1=0
while len(n)!=0:	
	n[0]=n[0]-nq[1]
	if n[0]<=0:
		cnt1=cnt1+nq[1]+n[0]
		print(t[0],cnt1)
		n.pop(0)
		t.pop(0)	
		
	else:
		n.append(n[0])
		t.append(t[0])
		n.pop(0)
		t.pop(0)
		cnt1+=nq[1]
### BUGGY CODE ###

n=int(input())
s=input()
l=len(s)
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
cnt=0
for j in range(2,l):
    for i in range(1,j):
        if j*2<=i+l:
            if s[i-1]!=s[j-1] and s[j-1]!=s[j*2-i-1] and s[i-1]!=s[j*2-i-1]:
                cnt+=1
print(ans-cnt)

### FIXED CODE ###

n=int(input())
s=input()
l=len(s)
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
cnt=0
for j in range(2,l):
    for i in range(1,j):
        if j*2<=i+l:
            if s[i-1]!=s[j-1] and s[j-1]!=s[j*2-i-1] and s[i-1]!=s[j*2-i-1]:
                cnt+=1
print(ans-cnt)