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

#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = []
    #2の倍数で割っていく
    z = 2
    while n%z==0 and (n>=z):
        cnt += 1
        n //= z
        
        A.append(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*2 <= N:
        if n%z == 0:
            cnt += 1
            n //= z
            A.append(z)
            
            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f
    
    #残ったnが以前に選んだもので割り切れないとき
    if n != 1 and all((n%i != 0 for i in A)):
        A.append(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)


### FIXED CODE ###

N = int(input())

def Prime_Factorize(n):
    primes = []
    while n%2 == 0:
        n//=2
        primes.append(2)
    f = 3
    while f*f <= n:
        if n%f == 0:
            n//=f
            primes.append(f)
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes

Primes = Prime_Factorize(N)
cnt = 0
for p in Primes:
    e = 1
    z = p
    while (N%z == 0) and (N >= z):
        N //= z
        e += 1 
        z = p**e
        cnt += 1
    while N%p == 0:
        N //= p
print(cnt)
### BUGGY CODE ###

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

cost = list()
for i in range(N):
    if i == 0:
        cost.append(0)
        continue
    step_min = 10**9
    for j in range(1,min(i+1,K+1)):
        step_cost = abs(a[i] - a[i-j]) + cost[i-j]
        step_min = step_cost if step_cost < step_min else step_min
    cost.append(step_min)

print(cost[-1])

### FIXED CODE ###

import numpy as np

N,K = map(int,input().split(' '))
a = np.array(list(map(int,input().split(' '))))

cost = np.full(N,10**9)
cost[0] = 0
for i in range(1 , N):
    
    size =  min(i,K)
    cost[i] = (np.abs(a[i] - a[i-size:i]) + cost[i-size:i]).min()

print(int(cost[-1]))
### BUGGY CODE ###

from collections import defaultdict
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0] -q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

#　aの逆元を求める
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def combination(m,k):
    res = 1
    for i in range(1,m+1):
        res = res*i%(10**9+7)
    for i in range(1,k+1):
        res = res*mod_inv(i,10**9+7)
    for i in range(1,m-k+1):
        res = res*mod_inv(i,10**9+7)
    return res%(10**9+7)

def main():
    n = int(input())
    ls = [int(x) for x in input().split()]
    cumsum = [0]*(n+1)
    for i in range(1,n+1):
        cumsum[i] = cumsum[i-1]+ls[i-1]
    cnt = defaultdict(int)
    for i in cumsum:
        cnt[i] +=1
    ans = 0
    for i in cnt.values():
        if i==1:
            continue
        ans += combination(i,2)
    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
    n = int(input())
    ls = [int(x) for x in input().split()]
    cumsum = [0]*(n+1)
    for i in range(1,n+1):
        cumsum[i] = cumsum[i-1]+ls[i-1]
    cnt = defaultdict(int)
    for i in cumsum:
        cnt[i] +=1
    ans = 0
    for i in cnt.values():
        if i==1:
            continue
        ans += int(i*(i-1)/2)
    print(ans)



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

A,B,C=map(int,input().split())
for i in range (A,B+1):
	if i<A+C or i>B-C:
		print(i)

### FIXED CODE ###

A,B,C=map(int,input().split())
L=[]
for i in range (C):
	if A+i>=A and A+i<=B:
		L.append(A+i)
	if B-i>=A and B-i<=B:
		L.append(B-i)
X=sorted(set(L))
for i in range (len(X)):
	print(X[i])
### BUGGY CODE ###

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

ans = 0
left = 0
right = 0
while left <= N-1:
    right = left
    xor = A[left]
    asum = A[left]
    for i in range(left+1, right):
        xor = xor ^ A[i]
        asum += A[i]
    while right <= N-1:
        if left == right or xor == asum:
            right += 1
            if right <= N-1:
                xor = xor ^ A[right]
                asum += A[right]
        else:
            break
    ans += right - left
    left += 1
print(ans)


### FIXED CODE ###

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

ans = 0
left = 0
right = 0
ex = 0
while left <= N-1:
    right = max(left, right)
    while right <= N-1:
        if ex + A[right] == ex ^ A[right]:
            ex += A[right]
            right += 1
        else:
            ex -= A[left]
            break
    ans += right - left
    left += 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()))

    gcdnum = 1
    gcd = math.gcd

    for a in A:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        ans += a
        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 ###

from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

a_cnt = Counter(a)

a_comb = {}
for key, val in a_cnt.items():
    if val >= 2:
        a_comb[key] = combinations_count(val, 2)
    else:
        a_comb[key] = 0


for num in a:
    dic = a_comb.copy()
    if dic[num] <= 1:
        dic[num] = 0
    else: 
        dic[num] = combinations_count(a_cnt[num]-1, 2)
    print(int(sum(dic.values())))

### FIXED CODE ###

from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

a_cnt = Counter(a)

a_comb = {}
for key, val in a_cnt.items():
    if val >= 2:
        a_comb[key] = combinations_count(val, 2)
    else:
        a_comb[key] = 0

sum_v = sum(a_comb.values())

for num in a:
    print(sum_v-a_cnt[num]+1)
### BUGGY CODE ###

N,K=map(int,input().split())
D=list(map(int,input().split()))
DE=list(map(lambda i :(1+i)/2,D))
DS=[]
A=[]
for i in range(0,N-K+1):
    DS.append(sum(DE[0:i+K])-sum(DE[0:i]))
ans=max(DS)
print(ans)



### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
pE=list(map(lambda i :(1+i)/2,p))
pA=[sum(pE[0:K])]
inter=sum(pE[0:K])
for i in range(0,N-K):
    inter=inter+pE[K+i]-pE[i]
    pA.append(inter)

ans=max(pA)
print(ans)
### BUGGY CODE ###

from fractions import gcd
n,m=map(int,input().split())
ans=1
for i in range(m//n+1)[::-1]:
  if gcd(m-i*(n-1),i)==i and ans==1:
    ans=i
    break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
def divisors(n):
  div=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      div.append(i)
      if not i==n//i:
        div.append(n//i)
  div=sorted(div)[::-1]
  return div
ans=1
for i in divisors(m):
  if m-i*(n-1)>0:
    ans=i
    break
print(ans)
### BUGGY CODE ###

R,C,K=map(int,input().split())
rcv=[list(map(int,input().split())) for _ in range(K)]

MAP=[[0 for _ in range(C)] for _ in range(R)]
DP=[[[0 for _ in range(4)] for _ in range(C)] for _ in range(R)]
for r,c,v in rcv:
    MAP[r-1][c-1]=v

DP[0][0][1]=MAP[0][0]
for i in range(R):
    for j in range(C):
        for num,point in enumerate([[1,0],[0,1]]):
            x,y=point
            X,Y=i+x,j+y
            if 0<=X<R and 0<=Y<C:
                for k in range(3):
                    if num==0:
                        DP[X][Y][1]=max(DP[X][Y][1],max(DP[i][j])+MAP[X][Y])
                    else:
                        DP[X][Y][k+1]=max(DP[X][Y][k+1],DP[X][Y][k],DP[i][j][k+1],DP[i][j][k]+MAP[X][Y])
print(max(DP[-1][-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

R,C,K=map(int,input().split())
J=[tuple(map(int,input().split())) for i in range(K)]

#DP0=[[0]*(C+2) for i in range(R+2)]
DP1=[[0]*(C+2) for i in range(R+2)]
DP2=[[0]*(C+2) for i in range(R+2)]
DP3=[[0]*(C+2) for i in range(R+2)]

MAP=[[0]*C for i in range(R)]

for x,y,v in J:
    MAP[x-1][y-1]=v

for i in range(R):
    for j in range(C):
        DP1[i][j]=max(DP1[i][j-1],DP1[i-1][j]+MAP[i][j],DP2[i-1][j]+MAP[i][j],DP3[i-1][j]+MAP[i][j])
        DP2[i][j]=max(DP2[i][j-1],DP1[i][j-1]+MAP[i][j])
        DP3[i][j]=max(DP3[i][j-1],DP2[i][j-1]+MAP[i][j])

ANS=0
for i in range(R):
    for j in range(C):
        ANS=max(ANS,DP1[i][j],DP2[i][j],DP3[i][j])
print(ANS)
### BUGGY CODE ###

N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

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

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

cost = [[0] * C for _ in range(3)]
for p in range(C):
    for i in range(N):
        for j in range(N):
            #グループごとにかかるコストの計算
            cost[(i+j)%3][p] += D[c[i][j]][p]

res = 10 ** 9
p = [0] * 3
for p[0] in range(C):
    for p[1] in range(C):
        if p[0] == p[1]:
            continue
        for p[2] in range(C):
            if p[2] == p[0] or p[1] == p[2]:
                continue
            tmp = 0
            for i in range(3):
                tmp += cost[i][p[i]]
            res = min(res, tmp)

print(res)
                


### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

cost = [[0] * C for _ in range(3)]
for p in range(C):
    for i in range(N):
        for j in range(N):
            #グループごとにかかるコストの計算
            cost[(i+j)%3][p] += D[c[i][j]][p]

res = 10 ** 9
p = [0] * 3
for p[0] in range(C):
    for p[1] in range(C):
        if p[0] == p[1]:
            continue
        for p[2] in range(C):
            if p[2] == p[0] or p[1] == p[2]:
                continue
            tmp = 0
            for i in range(3):
                tmp += cost[i][p[i]]
            res = min(res, tmp)

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

power = 1
n = int(input())
for i in range(n):
  power *= i + 1
print(power % 1000000007)


### FIXED CODE ###

import math
n = int(input())
print(math.factorial(n) % 1000000007)
### BUGGY CODE ###

import math
Q = int(input())

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

def is_prime(num):
  if(type(num) != type(0)):
    print('error at '+str(num)+' type = '+str(type(num)))
    print(type(int))
    return 0
  if(num<2):
    return 0
  elif(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = 100000#max(r)+1
  sn = [0]
  for i in range(1,MAXI+1,2):
    sn.append(is_prime(i) * is_prime(int((i+1)/2))) #odd
    sn.append(0) #even
  return sn

base = create_list()

for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

#!/usr/bin/env python3 ## -*- python -*-

def main():
    s = input()
    q = int(input())
    head = "l"
    for i in range(q):
        d = input()
        if d[0] == "1":
            if head == "l":
                head = "r"
            else:
                head = "l"
        else: # 2
            dd = d.split()
            f = int(dd[1])
            c = dd[2]
            if f == 1:
                if head == "l":
                    s = c + s
                else:
                    s = s + c
            else: # f == 2
                if head == "l":
                    s = s + c
                else:
                    s = c + s

    if head == "r":
        s = s[::-1]
    print(s)
main()

### FIXED CODE ###

#!/usr/bin/env python3 ## -*- python -*-
from collections import deque

def main():
    s = deque()
    s.extend(input())
    q = int(input())
    head = "l"
    for i in range(q):
        d = input()
        if d[0] == "1":
            if head == "l":
                head = "r"
            else:
                head = "l"
        else: # 2
            dd = d.split()
            f = int(dd[1])
            c = dd[2]
            if f == 1:
                if head == "l":
                    s.appendleft(c)
                else:
                    s.append(c)
            else: # f == 2
                if head == "l":
                    s.append(c)
                else:
                    s.appendleft(c)

    if head == "r":
        s.reverse()
    ans = ''.join(s)
    print(ans)
main()
### BUGGY CODE ###

import bisect
N,M=(int(x) for x in input().split())
As=sorted([int(x) for x in input().split()])
BC=[]

def i_sorted(L,num,hm):#ソート済み配列,入れる数,入れる個数
    pos=bisect.bisect_left(L,num)
    return L[:pos]+[num]*hm+L[pos:]

for _ in range(M):
    BC.append([int(x) for x in input().split()])

BC=sorted(BC, key=lambda x: x[1],reverse=True)
for lst in BC:
    if As[lst[0]-1]<=lst[1]:
        As=i_sorted(As[lst[0]:],lst[1],lst[0])
    else:
        pos=bisect.bisect_left(As,lst[1])
        As=i_sorted(As[pos:],lst[1],pos)
        
print(sum(As))


### FIXED CODE ###

import bisect
N,M=(int(x) for x in input().split())
As=sorted([int(x) for x in input().split()])
BC=[]

result=0
for _ in range(M):
    BC.append([int(x) for x in input().split()])

BC=sorted(BC, key=lambda x: x[1],reverse=True)
now=0
for b,c in BC:
    if now+b-1<=len(As)-1:
        if As[now+b-1]<=c:
            result+=c*b
            now+=b
        else:
            pos=bisect.bisect_left(As[now:],c)
            result+=c*pos
            now+=pos
            break
    else:
        if As[-1]<=c:
            result+=c*(N-now)
            As=[]
        else:
            pos=bisect.bisect_left(As[now:],c)
            result+=c*pos
            now+=pos
        break
        
print(result+sum(As[now:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
ans = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    ans[l][r] += 1

for i in range(1, N+1):
    for j in range(N):
        ans[i][j+1] += ans[i][j]

for _ in range(Q):
    l, r = map(int, input().split())
    res = 0
    for i in range(l, r+1):
        res += ans[i][r]
    print(res)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
ans = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    ans[l][r] += 1

for i in range(1, N+1):
    for j in range(N):
        ans[i][j+1] += ans[i][j]

for _ in range(Q):
    l, r = map(int, input().split())
    res = 0
    for i in range(l, r+1):
        res += ans[i][r]
    print(res)
### BUGGY CODE ###

def main():
    k, s = map(int, input().split())
    # print(k, s)
    ans = 0
    for z in range(k, -1, -1):
        for y in range(k, -1, -1):
            for x in range(k, -1, -1):
                if x + y + z == s:
                    ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    k, s = map(int, input().split())
    # print(k, s)
    ans = 0
    for z in range(k+1):
        if z <= s:
            for y in range(k+1):
                x = s - z - y
                if 0 <= x and x <= s and x <= k:
                    ans += 1
    print(ans)


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

from collections import Counter

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

counter = Counter(S)
r_count = counter['R']
g_count = counter['G']
b_count = counter['B']

ans = r_count * g_count * b_count
for i in range(N):
    for j in range(N):
        k = 2 * j - i
        if k > N-1:
            break
        if i < j < k and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

counter = Counter(S)
r_count = counter['R']
g_count = counter['G']
b_count = counter['B']

ans = r_count * g_count * b_count
for i in range(N):
    for j in range(N):
        k = 2 * j - i
        if k > N-1:
            break
        if i < j < k and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

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

h,n,*L=map(int,open(0).read().split())
dp=[0]+[9e9]*h
ov=9e9
for a,b in zip(*[iter(L)]*2):
	for i in range(h):
		if a+i>h:
			ov=min(min(dp[i:])+b,ov)
			break
		t=dp[i]+b
		if t<dp[i+a]:
			dp[i+a]=t
print(min(ov,dp[h]))

### FIXED CODE ###

h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))
### BUGGY CODE ###

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

ans = 1
for i in range(len(a)):
    ans *= a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)



### FIXED CODE ###

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

ans = 1
if 0 in a:
    ans = 0
else :
    for i in a:
        if  ans * i > 10**18:
            ans = -1
            break
        else:
            ans *= i

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

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    from bisect import bisect_right as br
    c=br(A,A[-1]//2)
    for a in A:
        kou=a*kou//gcd(a,kou)
    for a in range(min(c+1,n)):
        if (kou//A[a])%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()