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

import bisect
kyaku, teiin, jikan = map(int, input().split(" "))
a=sorted([(int)(input()) for i in range(kyaku)])
count = 0
while(True):
  #print(a)
  if len(a) > teiin:
    if a[0] + jikan >= a[teiin]:
      a = a[teiin:]
    else:
      a = a[bisect.bisect_left(a, a[0] + jikan):]
  else:
    if a[0] + jikan >= a[-1]:
      count += 1
      break
    else:
      a = a[bisect.bisect_left(a, a[0] + jikan):]
  count += 1
print(count)

### FIXED CODE ###

n,c,k = map(int ,input().split(" "))
t = sorted([int(input()) for i in range(n)])
total = 0
count = 0
while(count != n):
  temp = 0
  #print(count, total)
  for i in range(c):
    if count + i >= n:
      #print("乗りたい人数を全部さばいた")
      if t[-1] - t[count] <= k:
        #print("最後の人全員載せる")
        count = n
        total += 1
        break
      else:
        temp = 0
        while(count != n):
          #print("残りを何回で載せられるか")
          if t[count + temp] - t[count] <= k:
            temp += 1
          else:
            count += temp + 1
            total += 1
        break
      break
    if t[count + i] - t[count] > k:
      #print("定員を超えた")
      count += i
      total += 1
      break
  else:
    #print("k人全員載せる")
    count += c
    total += 1
    if count == n:
      break
print(total)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    E[v].sort()
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
for v in range(1, N):
    available = set(range(1, K+1))
    for u in E[v]:
        if v > u:
            e_idx = edge_idx[(u, v)]
            available -= set([edge_color[e_idx]])
            continue
        e_idx = edge_idx[(v, u)]
        c = list(available)[0]
        edge_color[e_idx] = c
        available -= set([c])
for i in range(N-1):
    print(edge_color[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
q = deque([(-1, 1)])
visited = {i: False for i in range(1, N+1)}
while q:
    p, v = q.popleft()
    visited[v] = True
    if p == -1:
        used = -1
    else:
        used = edge_color[edge_idx[(p, v)]] if p < v else edge_color[edge_idx[(v, p)]]
    c = 1
    for u in E[v]:
        if visited[u]: continue
        q.append((v, u))
        if c == used: c += 1
        if u < v:
            edge_color[edge_idx[(u, v)]] = c
        else:
            edge_color[edge_idx[(v, u)]] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])
### BUGGY CODE ###

k = int(input())
start = 7
def judge(l, x):
  if l % x == 0:
    return True
  else:
    return False

def long7(i):
  x = "7"*i
  return int(x)


if k % 2 == 0:
  print("-1")
  exit()

cnt = len(str(k)) -1
          

          
for i in range(len(str(k)), 10000000):
  l = long7(i)
  cnt += 1
  if judge(l, k) == True:
    print(cnt)
    exit()

### FIXED CODE ###

k = int(input())
start = 7
if k % 2 == 0:
  print("-1")
  exit()
for i in range(k + 1):
  if start % k == 0:
    print(i + 1)
    exit()
  start = (start * 10 + 7) % k
print("-1")
### BUGGY CODE ###

while True:
    try:
        N, M = map(int, input().split())
        a = [int(input()) for _ in range(M)]
        
        if (1 in a):
            f = [1, 0]
        else:
            f = [1, 1]
            
        for i in range(2, N+1):
            if i in a:
                f.append(0)
            else:
                f.append((f[i-1] + f[i-2])%1000000007)
        
        print(f[N])
    except:
        break

### FIXED CODE ###

mod = 1000000007

while True:
    try:
        N, M = map(int, input().split())
        
        # check obstacles: O(1)
        a = [0] * (N+1)
        for _ in range(M):
            a[int(input())] = 1
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 0 if a[1] else 1
        
        for i in range(2, N+1):
            if a[i]:
                dp[i] = 0
            else:
                dp[i] = dp[i-1] + dp[i-2]
        
        print(dp[N] % mod)
    except:
        break
### BUGGY CODE ###

N = int(input())
S = input()
l = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(min(j - i, N - j + 1) + 1):
            if S[i : i + k] == S[j : j + k] :
                pass
            else:
                break
            l = max(l,  k)     
print(l)

### FIXED CODE ###

N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)
### BUGGY CODE ###

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

ans=""
for i in range(1, n+1):
  ans = ans + str(a.index(i)+1) + " "
  
print(ans.strip())


### FIXED CODE ###

n = int(input())
ans=[0] * (n + 1)

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

for i in range(1, n+1):
  chakujunn = a[i-1]
  ans[chakujunn] = i
  
print(" ".join(map(str,ans[1:])))
### BUGGY CODE ###

import numpy as np
n=int(input())
s=np.array([list(input()) for i in range(n)])
l=np.zeros((n,n),dtype=np.str)
ans=0
for i in range(n):
    l[:i]=s[n-i:n]
    l[i:]=s[:n-i]
    t=False
    for x in range(n):
        for y in range(x+1,n):
            if l[x][y]!=l[y][x]:
                t=True
                break
        if t:
            break
    if not t:
        ans+=n

print(ans)


### FIXED CODE ###

import numpy as np
n=int(input())
s=np.array([list(input()) for i in range(n)])
s=np.concatenate([s,s])
ans=0
for i in range(n):
    l=s[i:i+n]
    if (l==l.T).all():
        ans+=n
print(ans)
### BUGGY CODE ###

import numpy as np

N,K = map(int,input().split())
A = np.array(list(map(int,input().split())))
F = np.array(list(map(int,input().split())))

A = np.sort(A)
F = np.sort(F)[::-1]
Amax = A[-1]
Fmax = F[0]
x=0

if np.sum(A) < K:
    x = 0
else:
    xl = 0
    xh = Amax*Fmax
    while xh-xl > 0:
        xm = int((xl+xh)//2)
        if np.sum(np.max(A[i]-xm//F[i] ,0) for i in range(0,N)) > K: 
            xl = xm + 1
        else: 
            xh = xm
    else:
        x = xl
print(x)            


### FIXED CODE ###

import numpy as np

N,K = map(int,input().split())
A = np.sort(list(map(int,input().split())))
F = np.sort(list(map(int,input().split())))[::-1]

Amax = A[-1]
Fmax = F[0]

x=0
if sum(A) < K:
    x = 0
else:
    xl = 0
    xh = Amax*Fmax
    while xh-xl > 0:
        xm = int((xl+xh)//2)
        AF = A-xm//F 
        if np.sum(AF[AF>0]) > K: 
            xl = xm + 1
        else: 
            xh = xm
    else:
        x = xl
print(x)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

index = 0
result = 0
while True:
    num = A.count(A[index])
    index += num
    if (num % 2) == 1:
        result += 1
    if N <= index:
        break
print(result)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()


def customCount(idx):
    target = A[idx]
    cnt = 1
    idx += 1
    while True:
        if idx == N or A[idx] != target:
            return cnt
        else:
            idx += 1
            cnt += 1


index = 0
result = 0
while True:
    num = customCount(index)
    index += num
    if (num % 2) == 1:
        result += 1
    if N <= index:
        break
print(result)
### BUGGY CODE ###

MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    tmp = nPr(m-k, n-k)
    tmp *= tmp
    tmp %= MOD
    tmp *= nPr(m, k)
    tmp %= MOD
    tmp *= nCr(n,k)
    tmp %= MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans += MOD
ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    tmp = nPr(m-k, n-k)
    tmp *= tmp
    tmp %= MOD
    tmp *= nPr(m, k)
    tmp %= MOD
    tmp *= nCr(n,k)
    tmp %= MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans += MOD
ans %= MOD
print(ans)
### BUGGY CODE ###

s = input()
t = input()

def replacement(word, a, b):
    return word.replace(a, "0").replace(b, a).replace("0", b)

yet_list = []
for i in range(len(s)):
    if s[i] != t[i]:
        if not s[i] in yet_list:
            s = replacement(s, s[i], t[i])
            yet_list.append(s[i])
if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
t = input()
yetlist = {}
yetlist2 = {}
for i in range(len(s)):
    if s[i] in yetlist:
        if t[i] != yetlist[s[i]]:
            print("No")
            sys.exit()
    else:
        yetlist[s[i]] = t[i]
    if t[i] in yetlist2:
        if s[i] != yetlist2[t[i]]:
            print("No")
            sys.exit()
    else:
        yetlist2[t[i]] = s[i]   
            
print("Yes")
### BUGGY CODE ###

N, Y = map(int, input().split())
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            t = (i, j, k)
            if i+j+k == N:
                if Y == i*10000 + j*5000 + k*1000:
                    print(i, j, k)
                    exit()
print('-1 -1 -1')

### FIXED CODE ###

N, Y = map(int, input().split())
for i in range(N+1):
    for j in range(N-i+1):
        k = N - i - j
        t = (i, j, k)
        if Y == i*10000 + j*5000 + k*1000:
           print(*t)
           exit()
print('-1 -1 -1')
### BUGGY CODE ###

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

ans = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                if j-i != k-j:
                    ans +=1
print(ans)

### FIXED CODE ###

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

R_count = S.count('R')
G_count = S.count('G')
B_count = S.count('B')

ans = R_count * G_count * B_count

for i in range(N-2):
    for d in range(1,N):
        if i+2*d >= N:
            break
        else:
            j = i+d
            k = j+d
            
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

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

S = list(map(int, input()))
n = len(S)
 
fl = [False]*(n+1)
res = 0
 
for i in range(n-3):
    if fl[i]:
        continue
    
    x = 0
    cnt = 0
    for j in range(i, n):
        x *= 10
        x += S[j]
        x %= 2019
        if x == 0:
            cnt += 1
            fl[j+1] = True
            
    
    res += (cnt+1)*cnt//2
 
print(res)

### FIXED CODE ###

S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

str_list = stdin.readline().rstrip().split()
int_list = int_data = [int(i) for i in str_list]

cnt_list = []
ret_list = []

for i in range(1, N+1):
    tmp_cnt = int_list.count(i)
    cnt_list.append(tmp_cnt)
    
tmp_ans = 0
for i in range(N):
    if cnt_list[i] < 2:
        continue
    else:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list.append(tmp_ret)

for i in int_list:
    print(ret_list[i-1])

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])
### BUGGY CODE ###

from collections import defaultdict
from collections import deque

n,x,y = map(int,input().split())
graph=[[] for _ in range(n)]

for i in range(1,n+1):
    if i!=x:
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
    else:
        graph[i-1].append(y)
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
k_dic=defaultdict(int)

for i in range(1,n):
    q = deque([[i]])
    prev = [0]*n
    prev[i-1] = 1
    dic=defaultdict(int)
    while q:
        now_l = q.popleft()
        tu = []
        for now in now_l:
            nex = graph[now-1]
            
            for ne in nex:
                if prev[ne-1] == 0:
                
                    tu.append(ne)
                    q.append(tu)
                    prev[ne-1] = 1
                    dic[ne] = dic[now]+1
                    if ne > i:
                        k_dic[dic[ne]] += 1

for i in range(1,n):
    print(k_dic[i])




### FIXED CODE ###

from collections import defaultdict
from collections import deque

n,x,y = map(int,input().split())
graph=[[] for _ in range(n)]

for i in range(1,n+1):
    if i!=x:
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
    else:
        graph[i-1].append(y)
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
k_dic=defaultdict(int)

for i in range(1,n):
    q = deque([[i]])
    prev = [0]*n
    prev[i-1] = 1
    dic=defaultdict(int)
    while q:
        now_l = q.popleft()
        tu = []
        for now in now_l:
            nex = graph[now-1]
            
            for ne in nex:
                if prev[ne-1] == 0:
                
                    tu.append(ne)
                    q.append(tu)
                    prev[ne-1] = 1
                    dic[ne] = dic[now]+1
                    if ne > i:
                        k_dic[dic[ne]] += 1

for i in range(1,n):
    print(k_dic[i])
### BUGGY CODE ###

import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight_value = [list(map(int, input().split())) for _ in range(N)]
# print(lst_weight_value)

# def chmax(a, b):
#     if a >= b:
#         return a
#     else:
#         return b

# 重さwの品物の入れ方で達成できる価値の最大値
dp = [0] * (W + 1)

for i in range(N):
    weight, value = lst_weight_value[i]
    for w in range(W, -1, -1):
        _w = w + weight
        _v = dp[w] + value
        if _w > W:
            continue
        if _v <= dp[_w]:
            continue
        dp[_w] = _v

print(dp[-1])

### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
sum = 0
for a in range(1,K+1) :
    for b in range(1,K+1) :
        for c in range(1,K+1) :
            sum += gcd(a, b, c)

print(sum)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
sum = K ** 2
for a in range(2,K+1) :
    for b in range(1,K+1) :
        if gcd(a,b) == 1 :
            sum += K
        else :
            for c in range(1,K+1) :            
                sum += gcd(a, b, c)
            
print(sum)
### BUGGY CODE ###

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

mod=1000000007
n=input();
arr = list(map(int, raw_input().split()))
l=arr[0];
for i in arr:
    x=gcd(l,i)
    l=(l*i)/x
    
ans=0
#print l
for i in arr:
    b=l/i
    ans=(ans%mod + b%mod)%mod
ans=(ans%mod +mod)%mod
print ans


### FIXED CODE ###

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

mod=1000000007
n=input();
arr = list(map(int, raw_input().split()))
l=arr[0];
for i in arr:
    x=gcd(l,i)
    l=(l*i)/x
    
ans=0
#print l
for i in arr:
    b=l/i
    ans+=b
ans=(ans%mod +mod)%mod
print ans
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0
# print(L)

for i in range(N-2):
    for j in range(i+1,N-1):
        start = j+1
        end = N
        while(start + 1 < end):
            if L[i] + L[j] > L[(start + end)//2]:
                start = (start + end)//2
            else:
                end = (start + end)//2
            # print(L[i],L[j],L[start],L[end-1])
        # print(i,j,start)
        if L[i] + L[j] > L[start]:
            ans += start - j
print(ans)


### FIXED CODE ###

import bisect

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

for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect.bisect_left(L,L[i]+L[j]) - j - 1
print(ans)
### BUGGY CODE ###

def f(x):
    return (a * x) // b - a * (x // b)


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

k = (n + 1) // b

ans = 0
for x in range(max(0, k * b - 1), n + 1):
    ans = max(ans, f(x))

print(ans)


### FIXED CODE ###

def f(x):
    return (a * x) // b - a * (x // b)


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

k = (n + 1) // b

x = max(k * b - 1, 0)
ans = f(x)
ans = max(ans, f(n))
print(ans)
### BUGGY CODE ###

n = int(input())
list = [int(i) for i in input().split()]
left = 1
right = 1
ans = 1
flag = True
for i in range(n):
    if i%2==0:
        right *= list[i]
    else:
        left *= list[i]

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


### FIXED CODE ###

n = int(input())
list = [int(i) for i in input().split()]

ans = 1
flag = True
for i in range(n):
    ans *= list[i]
    if ans>10**18:
        flag = False
        ans = ans%(10**18)
    if list[i]==0:
        flag = True
        break

if flag:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
# deli = [0]*N
# deli[- 1] = ls[-1][- 1]
deli = [ls[- 1][- 1]]
for i in range(N - 2, - 1, - 1):
    #deli[i] = max(deli[i - 1], ls[i][- 1])
    deli.append(max(deli[- 1], ls[i][- 1]))
    
deli = deli[::- 1]

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()

            if not group[node]:
                group[node] = count
    
            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)] 
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

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

import sys
sys.setrecursionlimit(10**7)
n=int(input())
# k=(n*(n+1))//2
l = list(map(float,input().split()))
dp=[[False for i in range(n+1)]for j in range(n+1)]
ans=0
def recur(h,t,n):
    if n==0:
        if h>t:
            global ans
            return 1
            
        return 0
    if dp[h][t]!=False:
        return dp[h][t]
    dp[h][t] = l[n-1]*recur(h+1,t,n-1)+recur(h,t+1,n-1)*(1-l[n-1])
    return dp[h][t]
print(recur(0,0,n))
    

### FIXED CODE ###

# import numpy as np
n=int(input())
l=[0]+list(map(float,input().split()))
n+=1
dp=[[0 for i in range(n)]for i in range(n)]
dp[0][0]=1
for i in range(1,n):
    for j in range(i+1):
        if j==0:
            dp[i][j] = (1-l[i])*dp[i-1][j]
        else:
            dp[i][j]=(1-l[i])*(dp[i-1][j])+l[i]*dp[i-1][j-1]
ans=0
# print(np.array(dp))
for i in range((n)//2,n):
    ans+=dp[-1][i]
print(ans)