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

import sys
import numpy as np
from functools import lru_cache
input = sys.stdin.readline

sys.setrecursionlimit(1000000)

N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])

XH.sort(key=lambda xh: xh[0])
XH = np.array(XH)

ans = 0 
while len(XH)>0:
	TRAGET = (XH[:,0] <= XH[0][0]+2*D)
	H = XH[0][1]
	if(0==H%A):
		a = H//A
	else:
		a = H//A+1
	XH[TRAGET] = XH[TRAGET] - [0,a*A]
	ans += a
	TRAGET = (XH[:,1] > 0)
	XH = XH[TRAGET]
print(ans)

### FIXED CODE ###

import sys
from collections import deque
 
input = sys.stdin.readline
 
N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])
 
XH.sort(key=lambda xh: xh[0])
que = deque()
D = 2*D
 
H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
que.append([XH[0][0]+D,a*A])
tot = a * A
ans = a
for i in range(1,N):
	while XH[i][0] > que[0][0] :
		tot -= que[0][1]
		que.popleft()
		if(len(que)==0): break
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
WV = []
for _ in range(N):
  w,v = map(int,input().split())
  WV.append([w,v])
for i in range(N):
  for w in range(W+1):
    if w >= WV[i][0]:
      dp[i+1][w] = max(dp[i][w -WV[i][0]]+WV[i][1],dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]
print(dp[N][W])

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

n = int(input())

list_A = []
for i in range(n):
    list_A.append(int(input()))

for i in range(len(list_A)):
    list_check = list_A[:i] + list_A[i+1:]
    print(max(list_check))

### FIXED CODE ###

n = int(input())

list_A = []
for i in range(n):
    list_A.append(int(input()))

#リスト内の最大の値を格納
max_val = max(list_A)

#リスト内の最大の値の位置を格納
for i in range(len(list_A)):
    if list_A[i] == max_val:
        max_val_position = i
        break

#リスト内のから最大の要素を除いた後の，最大の要素
max_val_2 = max(list_A[:max_val_position] + list_A[max_val_position+1:])

for i in range(len(list_A)):
    
    #リスト内の最大の数が除かれたときは二番目に大きい数を出力する
    if i == max_val_position:
        print(max_val_2)
    else:
        print(max_val)
### BUGGY CODE ###

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

#half_expo(a, n, mod) = (a**n) % mod
#二分累乗法
def half_expo_mod(a, n, mod):
    nbin = list(bin(n))
    nbin = nbin[3:]
    ans = a
    for j in nbin:
        if j == '0':
            ans **= 2
        else:
            ans = (ans ** 2) * a
        ans %= mod
    if n == 0: #n=0の時の処理
        ans = 1
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    return ans

ans = half_expo_mod(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

### FIXED CODE ###

#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

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

import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

n = ri()
a = rl()
N = 1000000
f = [0] * (N + 10)
for v in a:
    f[v] += 1
for i in range(N, 0, -1):
    if f[i] == 0:
        continue
    j = i * 2
    while j <= N:
        f[j] += f[i]
        j += i
cnt = sum(f[i] == 1 for i in a)
print(cnt)



### FIXED CODE ###

import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

n = ri()
a = rl()
N = 1000000
f = [0] * (N + 10)
for v in a:
    f[v] += 1
for i in range(N, 0, -1):
    if f[i] == 0:
        continue
    j = i * 2
    while j <= N:
        f[j] += f[i]
        j += i
cnt = sum(f[i] == 1 for i in a)
print(cnt)
### BUGGY CODE ###

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

D=[0]*100
C=0
W=[0]*10
R=len(set(S))**3

for i in range(N-2):
    if(C==R):
        break
    if(W[int(S[i])]<10):
        for j in range(i+1,N-1):
            if(W[int(S[i])]==10):
                break
            s=str(S[i])+str(S[j])
            if(D[int(s)]==0):
                D[int(s)]=1
                W[int(S[i])]+=1
                C+=len(set(S[j+1:N]))
print(C)



### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

def main():
    n = input()
    aa = []
    for _ in xrange(n):
        aa.append(input())
    bb = sorted(aa)
    b0, b1 = bb[-1], bb[-2]
    for a in aa:
        if a < b0:
            print b0
        else:
            print b1
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = input()
    aa = []
    for _ in xrange(n):
        aa.append(input())
    bb = sorted(aa)
    b0, b1 = bb[-1], bb[-2]
    for a in aa:
        if a < b0:
            print b0
        else:
            print b1
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)

### FIXED CODE ###

# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

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

def resolve():
    import numpy as np
    h, n = map(int, input().split())
    lab = np.zeros((n, 2), dtype=np.int)
    i = 0
    while True:
        try:
            a, b = map(int, input().split())
            lab[i][0] = a
            lab[i][1] = b
        except:
            break
        i += 1
    ma = np.max(lab[:, 0])
    dp = np.ones((n + 1, h + ma), dtype=np.int) * np.inf
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + ma):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j >= lab[i][0]:
                dp[i+1][j] = min(dp[i+1][j-lab[i][0]] + lab[i][1], dp[i+1][j])
    print(np.int(np.min(dp[1:, h:])))
resolve()

### FIXED CODE ###

def resolve():
    h, n = map(int, input().split())
    lab = []
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
        except:
            break
    cost = [0] * (h+1)
    for i in range(1, h+1):
        mb = 10 ** 8
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][1])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()
### BUGGY CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
INF = float("inf")
import sys,collections,heapq,math

N,K = map(int,sys.stdin.readline().split())
a = [[-b,b,1] for b in tuple(map(int,sys.stdin.readline().split()))] # single line with multi param
heapq.heapify(a)# a == [1,2,3]

for _ in range(K):
    _,ori,di = heapq.heappop(a)
    heapq.heappush(a, [-(ori)/(di+1),ori,di+1])

#print(a[0][0])
print(math.ceil(-a[0][0]))
# e = heapq.heappop(a) # e == 1
# heapq.heappush(a, 1) # a == [1,3,2]
# e = heqpq.heappushpop(a,4) # e == 1,a==[2,3,4]


### FIXED CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
INF = float("inf")
import sys,collections,heapq,math

N,K = map(int,sys.stdin.readline().split())
a = list(map(int,sys.stdin.readline().split())) # single line with multi param
a.sort(reverse=True)

ng = 0
ok = a[0]

def isOK(v):
    # within range
    # return key <= a[index]
    k = K
    i = 0
    while k >= 0 and i < N:
        #print("?",v,i,a[i],k,math.ceil(a[i] / v) -1,k - (math.ceil(a[i]/v) - 1))
        k = k - (math.ceil(a[i]/v) - 1)
        i += 1
    return k >= 0

while abs(ng-ok) > 1:
    mid = (ok+ng)//2
    #print(mid,isOK(mid))
    if isOK(mid):#ok condition?
        ok = mid #move ok
    else:
        ng = mid
#294924427
print(math.ceil(ok))

# a = [[-b,b,1] for b in tuple(map(int,sys.stdin.readline().split()))] # single line with multi param
# heapq.heapify(a)# a == [1,2,3]
# for _ in range(K):
#     _,ori,di = heapq.heappop(a)
#     heapq.heappush(a, [-(ori)/(di+1),ori,di+1])
# print(math.ceil(-a[0][0]))
### BUGGY CODE ###

# import numpy as np
from collections import deque

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

S=[input() for _ in range(H)]
# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
S = ['##{}##'.format(row) for row in S]
S.insert(0, '##{}##'.format('#' * W))
S.insert(0, '##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))


MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH+1,CW+1,0))
Cost[CH+1][CW+1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
# print(warp)

cost1 = deque()

while cost0:
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		dh = h+i
		dw = w+j
		if S[dh][dw] == '.' and c < Cost[dh][dw]:
			Cost[dh][dw] = c
			# print("updl ", i,j,dh,dw,c)
			cost0.appendleft((dh,dw,Cost[dh][dw]))

	if len(cost0) == 0:

		while cost1:
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				dh = h+i
				dw = w+j
				# print(i,j)
				if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
					Cost[dh][dw] = c + 1
					cost0.append((dh,dw,Cost[dh][dw]))


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 ###

MAX = pow(10,18)
n = int(input())
A = list(map(int,input().split()))

if 0 in A:
    print(0)
else:
    ans = 1
    for a in A:
        ans *= a
    if ans > MAX:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

MAX = pow(10,18)
def main():
    N = int(input())
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    for a in A:
        ans *= a
        if ans > MAX:
            print(-1)
            return

    print(ans)

main()
### BUGGY CODE ###

from math import gcd
from functools import reduce

def gcd_list(lis):
  return reduce(gcd, lis)

K = int(input())

ans = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += gcd_list([i,j,k])
      
print(ans)

### FIXED CODE ###

from math import gcd
from functools import reduce

def gcd_list(lis):
  return reduce(gcd, lis)

K = int(input())

ans = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += gcd_list([i,j,k])
      
print(ans)
### BUGGY CODE ###

import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

max_v_per_w = [0] * (W+1)
for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(max_v_per_w)
    for j in range(w, W+1):
        max_v_per_w[j] = max(tmp[j], tmp[j-w]+v)
        
print(max(max_v_per_w))



### FIXED CODE ###

N, W = map(int, input().split())
wv = [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 sum_w in range(W+1):
        weight = sum_w - wv[i-1][0]
        if weight < 0:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w]])
        else:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w], dp[i-1][weight]+wv[i-1][1]])
print(max(dp[N]))
### BUGGY CODE ###

k = int(input())

ans = 0
def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(gcd(i,j),s)

print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

import math

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

def gcd(x, y):
  z = x % y
  if z == 0:
    return y
  else:
    return gcd(y, z)
  
def common_divisors(x, y):
  gcd1 = 0
  if x == y:
    gcd1 = x
  elif x > y:
    gcd1 = gcd(x, y)
  else:
    gcd1 = gcd(y, x)
    
  divisors = []
  for i in range(1, gcd1):
    if x % i == 0 and y % i == 0:
      divisors.append(i)
  divisors.append(gcd1)
  return divisors

def make_divisors(n):
  divisors = [] 
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)
  return divisors

divisors = common_divisors(a, b)
divisors_set = frozenset(divisors)

res = []

for n in divisors:
  if n == 1 or n == 2 or n == 3:
    res.append(n)
  elif n % 2 == 0:
    continue
  else:
    dvs = set(make_divisors(n))
    if len(dvs) == 0 or not dvs <= divisors_set:
      res.append(n)

print("{}".format(len(res)))

### FIXED CODE ###

import math

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

def gcd(x, y):
  z = x % y
  if z == 0:
    return y
  else:
    return gcd(y, z)
  
def common_divisors(x, y):
  xd = make_divisors(x)
  xd.append(1)
  xd.append(x)
  yd = make_divisors(y)
  yd.append(1)
  yd.append(y)
  return set(xd).intersection(yd)

def make_divisors(n):
  divisors = [] 
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)
  return divisors

divisors = common_divisors(a, b)
divisors_set = frozenset(divisors)

res = []

for n in divisors:
  if n == 1 or n == 2 or n == 3:
    res.append(n)
  elif n % 2 == 0:
    continue
  else:
    dvs = set(make_divisors(n))
    if len(dvs) == 0 or not dvs <= divisors_set:
      res.append(n)

print("{}".format(len(res)))
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
count = 0
for r in range(N//R+1):
  for g in range((N-r*R)//G+1):
    b = (N-R*r-G*g)/B
    if b.is_integer() and b >= 0:
      count += 1
print(count)



### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
  for g in range((N-R*r)//G+1):
    if (N-R*r-G*g)%B == 0:
      cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
d=deque()
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            col = i*W+j
            d.append([i,j])
        while len(d)>0:
            v=d.popleft()
            x=v[0]
            y=v[1]
            dp[x][y]=col
            if x!=0:
                if (table[x][y]!=table[x-1][y])and(dp[x-1][y]==-1):
                    d.append([x-1,y])
            if x!=H-1:
                if (table[x][y]!=table[x+1][y])and(dp[x+1][y]==-1):
                    d.append([x + 1, y])
            if y!=0:
                if (table[x][y]!=table[x][y-1])and(dp[x][y-1]==-1):
                    d.append([x, y-1])
            if y!=W-1:
                if (table[x][y]!=table[x][y+1])and(dp[x][y+1]==-1):
                    d.append([x, y+1])
            #print(dp)
            #print(d)
            #input()
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1
#print(wlist,blist)
cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
seen=[[0 for _ in range(W)] for _ in range(H)]
d=deque()
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            col = i*W+j
            d.append([i,j])
            seen[i][j]=1
        while len(d)>0:
            v=d.popleft()
            x=v[0]
            y=v[1]
            dp[x][y]=col
            if x!=0:
                if (table[x][y]!=table[x-1][y])and(seen[x-1][y]==0):
                    seen[x-1][y]=1
                    d.append([x-1,y])
            if x!=H-1:
                if (table[x][y]!=table[x+1][y])and(seen[x+1][y]==0):
                    seen[x+1][y]=1
                    d.append([x + 1, y])
            if y!=0:
                if (table[x][y]!=table[x][y-1])and(seen[x][y-1]==0):
                    seen[x][y-1]=1
                    d.append([x, y-1])
            if y!=W-1:
                if (table[x][y]!=table[x][y+1])and(seen[x][y+1]==0):
                    seen[x][y+1]=1
                    d.append([x, y+1])
            #print(dp)
            #print(d)
            #input()
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1
#print(wlist,blist)
cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()