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

N, Q = map(int, input().split())
S = list(input())
qs = [list(map(int, input().split())) for _ in range(Q)]
for q in qs:
    count = 0
    string = S[q[0]-1:q[1]]
    indexes = [i for i, x in enumerate(string) if x == 'A']
    for i in indexes:
        try:
            if string[i+1] == 'C':
                count += 1
        except:
            pass
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = list(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt = [0]*N
is_a = False
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    cnt[i+1] = 1
for i in range(1, N):
  cnt[i] += cnt[i-1]

for l, r in lr:
  l -= 1
  r -= 1
  print(cnt[r]-cnt[l])
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    cities={}
    mem_city=[]
    for i in range(m):
        p, y = map(int, input().split())
        mem_city.append((p, y))
        if p in cities:
            cities[p].append(y)
        else:
            cities[p] = [y]
    #print(cities)
    for key in cities:
        cities[key].sort()
    #print(cities)

    for p, y in mem_city:
        idx = cities[p].index(y) + 1
        print("{:06d}{:06d}".format(p,idx))
    return

main()

### FIXED CODE ###

import sys

def main():
    n, m = map(int, input().split())
    lines = sys.stdin.readlines()

    cities = {}
    for i in range(m):
        p, y = map(int, lines[i].split())
        if p in cities:
            cities[p].append((i, y))
        else:
            cities[p] = [(i, y)]

    outputs = [None] * m
    for pref, city_list in cities.items():
        city_list.sort(key=lambda x: x[1])
        #print(pref, city_list)
        city_no = 1
        for city in city_list:
            outputs[city[0]] = "{:06d}{:06d}".format(pref, city_no)
            city_no += 1

    for output in outputs:
        print(output)
    return


main()
### BUGGY CODE ###

N,M = map(int,input().split())
ships = sorted([list(map(int,input().split())) for i in range(M)])

ans = "IMPOSSIBLE"

for i in range(M):
  if ships[i][0] == 1:
    ship = ships[i][1]
    for j in range(M):
      if ships[j][0] == ship and ships[j][1] == N:
        ans = "POSSIBLE"
        break
    else:
      continue
      
print(ans)

### FIXED CODE ###

def main():
  N,M = map(int,input().split())
  ships = [list(map(int,input().split())) for i in range(M)]
  start, goal = set(), set()
  for i in range(M):
    if ships[i][0] == 1:
      start.add(ships[i][1])
    if ships[i][1] == N:
      goal.add(ships[i][0])
  flg = start & goal
  print("POSSIBLE" if flg else "IMPOSSIBLE")
 
main()
### BUGGY CODE ###

def resolve():
    k, s = map(int, input().split())
    cnt = 0
    k += 1
    for i in range(k):
        for j in range(k):
            for l in range(k):
                if i+j+l == s:
                    cnt += 1
    print(cnt)
resolve()

### FIXED CODE ###

def resolve():
    k, s = map(int, input().split())
    cnt = 0
    for i in range(k+1):
        if i > s:
            break
        for j in range(k+1):
            if 0 <= s-i-j <= k:
                cnt += 1
            elif s-i-j < 0:
                break
    print(cnt)
resolve()
### BUGGY CODE ###

n=int(input())
a=[0]*n
a[:]=map(int,input().split())
for ii in range(n):
    print(a.count(ii+1))

### FIXED CODE ###

n=int(input())
a=[0]*(n-1)
a[:]=map(int,input().split())
b=[0]*(n)
"""print(a)
print(b)"""
for ii in range(n-1):
    b[a[ii]-1]+=1
for ii in range(n):
    print(b[ii])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=sum(a)
mi=10**15
for i in range(1,len(a)):
  s1=sum(a[0:i])
  s2=s-s1
  #print(s1,s2)
  mi=min([mi,abs(s1-s2)])
print(mi)

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
if(n==2):
  mi=abs(a[0]-a[1])
else:
  mi=10**15
  s1=a[0]
  for i in range(1,len(a)-1):
    s1+=a[i]
    s2=s-s1
    #print(s1,s2)
    mi=min([mi,abs(s1-s2)])
print(mi)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)

gaps = np.array(gaps, np.int)  # 整数列に変換
if 0 in gaps:
    print(0)
else:
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fib(gaps[i]-1)
    print(patterns % 1000000007)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  # 整数列に変換



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

q = []
sm = []

for value in p:
    q.append((value + 1) / 2)

for i in range(N-K+1):
    sm.append(sum(q[i:i+K]))

print(max(sm))

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

q = []

for value in p:
    q.append((value + 1) / 2)

sm = [sum(q[:K])]
for i in range(1, N-K+1):
    sm.append(sm[-1] - q[i-1] + q[i+K-1])

print(max(sm))
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K + 1):
    pass
    for y in range(K + 1):
        pass
        for z in range(K + 1):
            if x + y + z == S:
                cnt += 1
print(cnt)


### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if z >= 0 and z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

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

import itertools
c = itertools.combinations(A, 2)
q=0
for v in c:
    q +=v[0]*v[1]%MOD
print(q%MOD)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
B=0
tem = sum(A)
for i in range(len(A)):
    tem -= A[i]
    B+= (A[i]%MOD)*(tem%MOD)
print(B%MOD)
### BUGGY CODE ###

MOD = 10**9+7

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

Ci = n
Si = n
Ai = 0
Bi = 0

if a == 1:
    Ai = Ci
if b == 1:
    Bi = Ci
    
for k in range(2,n+1):
    Ci = ((Ci)*(n-k+1) % MOD)//k
    #Ci %= MOD
    Si += Ci
    Si %= MOD
    if k == a:
        Ai = Ci
    if k == b:
        Bi = Ci

ans = (Si - Ai - Bi) % MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7

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

Sn = pow(2,n,MOD) - 1
if a > b:
    a,b = b,a
Xa, Xb = 1,1
Ya, Yb = 1,1
for i in range(b):
    if i < a:
        Xa = ( Xa * (n-i) ) % MOD
        Ya = ( Ya * pow((a-i),MOD-2, MOD)) % MOD
    Xb = ( Xb * (n-i) ) % MOD
    Yb = ( Yb * pow((b-i),MOD-2, MOD)) % MOD

ans = Sn - Xa*Ya % MOD - Xb*Yb % MOD
while ans < 0:
    ans += MOD
    
print(ans)
### BUGGY CODE ###

n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])
### BUGGY CODE ###

N = int(input())
ans = int(0)
A =[[0 for i in range(N)] for j in range(N)]
Lcandi = []
count =int(0)
Ln = int(0)
Lm = int(N*(N-1)//2)

for i in range(N):
    A[i] = list(map(int,input().split()))

while Ln<Lm:
    Lcandi = []
    Lnc = int(0)
    for i in range(N):
        if len(A[i]) != 0:
            if i+1 < A[i][0]:
                if not ([i+1,A[i][0]]) in Lcandi:
                    Lcandi.append([i+1, A[i][0]])
                else:
                    A[A[i][0]-1].remove(i+1)
                    A[i].remove(A[i][0])
                    Lnc +=1

            else:
                if not ([A[i][0],i+1]) in Lcandi:
                    Lcandi.append([A[i][0],i+1])
                else:
                    z=int(0)
                    z=A[i][0]
                    A[z-1].remove(i+1)
                    A[i].remove(A[i][0])
                    Lnc +=1

    if Lnc ==0:
        print("-1")
        exit()
    Ln += Lnc
    count +=1

print(count)




### FIXED CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    #A = [LI() for _ in range(N)]
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-1を返す
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  # ループがあれば-1を返す（問題文の指示）
            return
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a2 = sorted(a, reverse=True)

b = list(map(int, input().split()))
b2 = sorted(b, reverse=True)

c = list(map(int, input().split()))
c2 = sorted(c, reverse=True)

cnt = 0
for x in a2:
    for y in b2:
        if x >= y:
            break
        #x < y
        for z in c2:
            if y >= z:
                break
            #y < z
            cnt += 1
print(cnt)

### FIXED CODE ###

'''
https://beta.atcoder.jp/contests/abc077/submissions/2532572
'''
from bisect import bisect_left, bisect_right

def inpl():
    return list(map(int, input().split()))

n = int(input())
a = sorted(inpl())
b = sorted(inpl())
c = sorted(inpl())

ans = 0
for v in b:
    ans += bisect_left(a, v) * (n - bisect_right(c, v))
print(ans)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = []
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B.append(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N * 0.99 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-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 ###

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

n4 = []
n2 = set()
for a in A:
    if A.count(a) >= 4:
        if len(n4) >= 1:
            break
        n4.append(a)
    elif A.count(a) >= 2:
        if len(n2) >= 2:
            break
        n2.add(a)
n2 = list(n2)

ans = 0
if len(n2) >= 2:
    ans = n2[0] * n2[1]
for i in n4:
    for j in n2:
        ans = max(ans, i*j)
if len(n4) >= 1:
    ans = max(ans, n4[0] ** 2)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
kouho = set()

for i in range(N):
    if i == 0:
        continue
    elif A[i-1] == A[i]:
        kouho.add(A[i])
        if A.count(A[i]) >= 4 or len(kouho) >= 2:
            break
else:
    ans = 0

kouho = list(kouho)

if len(kouho) >= 2:
    ans = kouho[0] * kouho[1]
elif len(kouho) == 1:
    ans = kouho[0] ** 2

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

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
if x_max < a:
    print(0)
else:
    dp = [[[0 for k in range(x_sum + 1)] for j in range(n + 1)] for i in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        for j in range(n + 1):
            for k in range(x[i - 1]):
                dp[i][j][k] = dp[i - 1][j][k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 1):
                    dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]]

    ans = 0
    for j in range(1, min(x_sum // a + 1, n + 1)):
        ans += dp[-1][j][j * a]
    print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
ans = 0
if x_max >= a:
    dp = [[0 for j in range(2 * x_sum + 1)] for i in range(2)]
    dp[0][x_sum] = 1
    for i in range(1, n + 1):
        idx = i % 2
        y = x[i - 1] - a
        for j in range(2 * x_sum + 1):
            if 0 <= j - y <= 2 * x_sum:
                dp[idx][j] = dp[1 - idx][j] + dp[1 - idx][j - y]
            else:
                dp[idx][j] = dp[1 - idx][j]
    ans = dp[n % 2][x_sum] - 1
print(ans)
### BUGGY CODE ###

#coding:utf-8

s = input()
s_arr = list(s)

n = 0
l = len(s_arr)
while True:
    counter = 0
    for i in range(l):
        if i == l-1:
            break
        if s_arr[i] == 'B':
            if s_arr[i+1] == 'W':
                s_arr[i] = 'W'
                s_arr[i+1] = 'B'
                counter += 1
                n += 1
    if counter == 0:
        break
print(n)

### FIXED CODE ###

#coding:utf-8

s = input()
s_arr = list(s)

n = 0
l = len(s_arr)

ans = 0
b_count = 0
for i in range(l, 0, -1):
    if i == l:
        if s_arr[i-1] == 'B':
            b_count += 1
    else:
        if s_arr[i-1]=='B':
            ans += l - i - b_count
            b_count += 1


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

import sys
n = int(input())
a = list(map(int, input().split()))
i = 0
while(True):
  for x in a:
    if x%2!=0:
      print(i)
      sys.exit()
    else:
      x = x//2
  i += 1


### FIXED CODE ###

import sys
def main():
    n = int(input())
    a = list(map(int, input().split()))
    i = 0
    while(True):
        for x in a:
            if x%2!=0:
                print(i)
                sys.exit()

        a = [x//2 for x in a]
        i += 1

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

N=int(input())
P=[None]*N
for i in range(N):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

ZOUKA=[0]*(N+1)

for i in range(1,N+1):
    if ZOUKA[i]==-1:
        continue
    
    r=i
    for j in range(N):
        if P[j]==r:
            r+=1
            ZOUKA[i]+=1
            break

    for k in range(j+1,N):
        if P[k]==r:
            ZOUKA[r]=-1
            r+=1
            ZOUKA[i]+=1

Ans=N-max(ZOUKA)
print(Ans)


### FIXED CODE ###

N=int(input())
P=[None]*(N+1)
for i in range(1,N+1):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

Q=[0]*(N+2)

for i in range(1,N+1):
    Q[P[i]]=i

count=0
Ans=0
for i in range(1,N+2):
    if Q[i]>Q[i-1]:
        count+=1
    else:
        Ans=max(count,Ans)
        count=1

print(N-Ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**9)

def dfs(num,lis,count,target):
    visited[num]=count
    n_city=A[num]
    if visited[n_city]!=-1:
        lis.append(num)
        if target<=count:
              print(lis[target]+1)
        else:
            rep=len(lis)-visited[n_city]
            target-=visited[n_city]
            amari=target%rep
            temp=lis[visited[n_city]:]
            print(temp[amari]+1)
        exit()
    else:
        dfs(n_city,lis+[num],count+1,target)
    

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=list(map(lambda x:x-1,A))

visited=[-1]*N

dfs(0,[],0,K)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**9)

def dfs(num,lis,count,target):
    visited[num]=count
    n_city=A[num]
    if visited[n_city]!=-1:
        lis.append(num)
        if target<=count:
              print(lis[target]+1)
        else:
            rep=len(lis)-visited[n_city]
            target-=visited[n_city]
            amari=target%rep
            temp=lis[visited[n_city]:]
            print(temp[amari]+1)
        exit()
    else:
        lis.append(num)
        dfs(n_city,lis,count+1,target)
    

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=list(map(lambda x:x-1,A))

visited=[-1]*N

dfs(0,[],0,K)
### BUGGY CODE ###

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    for m in M:
        for j in range(n):
            w = rec(m,A[j:])
            if w:
                break
        if w:
            print "yes"
        else:
            print "no"

def rec(m,A):
    r1 = rec1(m,A)
    r2 = rec1(m-A[0],A)

    if r1 or r2:
        return True
    else:
        return False

def rec1(m_new,A):
    if m_new == 0:
        return True
    elif m_new < 0:
        return False
    else:
        if len(A) == 1:
            return False
        else:
            return rec(m_new,A[1:])
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
cnt=0
while True:
    for i, a in enumerate(A):
        if A[i] != i+1:
            A.pop(i)
            cnt+=1
            break
    else:
        break

if len(A)==0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
cnt=0
i=1
for a in A:
    if a ==i:
        i+=1
 
ans =n-i+1
if ans ==n:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    P=list(map(float,input().split()))
    dp=[[0]*(n+1) for _ in range(n)]#コインi(0-)までで，j枚が表
    dp[0][0]=1-P[0]
    dp[0][1]=P[0]
    for i in range(1,n):
        for j in range(i+2):
            if j==0:
                dp[i][j]=dp[i-1][j]*(1-P[i])
            else:
                dp[i][j]=dp[i-1][j-1]*P[i]+dp[i-1][j]*(1-P[i])
    print(sum(dp[-1][n//2+1:]))
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    P=list(map(float,input().split()))
    dp=[[0]*(n+1) for _ in range(n)]#コインi(0-)までで，j枚が表
    dp[0][0]=1-P[0]
    dp[0][1]=P[0]
    for i in range(1,n):
        for j in range(i+2):
            if j==0:
                dp[i][j]=dp[i-1][j]*(1-P[i])
            else:
                dp[i][j]=dp[i-1][j-1]*P[i]+dp[i-1][j]*(1-P[i])
    print(sum(dp[-1][n//2+1:]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(raw_input())
d = 2
count = 0 
def f(c):
	
	cumul = 0
	step = 1
	stack = []
	while(cumul < c):
		stack.append(step)
		cumul += step
		step += 1
	if cumul > c:
		cumul -= stack.pop()
	return len(stack)



while(n != 1):
	if n%d==0:
		c = 0
		while(n%d == 0): 
			c += 1
			n /= d
		count += f(c)
	d+=1
print count

### FIXED CODE ###

def f(exponent):
	#reurns how many times a prime raised to exponent can be used
	step = 1
	cumul = 0
	count = 0
	while( cumul <= exponent):
		cumul += step
		count +=1
		step +=1
	return count - (1 if cumul > exponent else 0)

def answer(n):
	if n == 1: return 0
	res = 0
	on = n
	p = True
	for d in range(2, int(on ** 0.5) + 2):
		if n % d == 0:
			p = False
			e = 0
			while(n%d == 0): 
				e +=1
				n/=d
			res+= f(e)
	if n > 1: res += 1
	return res

print answer(int(raw_input()))
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    s = gete()
    t = gete()

    dp = [[""] * (len(t) + 1) for _ in range(len(s) + 1)]

    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if si == tj:
                dp[i + 1][j + 1] = dp[i][j] + si
            else:
                x, y = dp[i][j + 1], dp[i + 1][j]
                dp[i + 1][j + 1] = x if len(x) > len(y) else y

    print(dp[len(s)][len(t)])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    s = gete()
    t = gete()
    ans = ""

    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if si == tj:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    i, j = len(s), len(t)

    ans_r = ""
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            ans_r += s[i - 1]
            i -= 1
            j -= 1
        elif dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1

    print(ans_r[::-1])


if __name__ == "__main__":
    main()