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

import numpy as np

N, M, Q = map(int, input().split())
N_Map = np.zeros((N + 1, N + 1))
for _ in range(M):
    a = list(map(int, input().split()))
    N_Map[:a[0] + 1, a[1]:] += 1

result = []
for _ in range(Q):
    a = list(map(int, input().split()))
    result.append(N_Map[a[0], a[1]])
for r in result:
    print(int(r))

### FIXED CODE ###

N, M, Q = map(int, input().split())
N_Map = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

for _ in range(M):
    a = list(map(int, input().split()))
    N_Map[a[0]][a[1]] += 1

for i in range(N, 0, -1):
    count = 0
    for j in range(1, N  + 1):
        count += N_Map[i][j]
        if i < N:
            N_Map[i][j] = N_Map[i + 1][j] + count
        else:
            N_Map[i][j] = count

Pi = []
for _ in range(Q):
    a = list(map(int, input().split()))
    Pi.append(a)

for p in Pi:
    print(N_Map[p[0]][p[1]])
### BUGGY CODE ###

mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*3**qleft + qleft*3**(qleft-1)
        else: 
            LEFT = a*3**qleft
        if qright > 0:
            RIGHT = c*3**qright + qright*3**(qright-1)
        else:
            RIGHT = c*3**qright
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)

### FIXED CODE ###

mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*pow(3,qleft,mod) + qleft*pow(3,qleft-1,mod)
        else: 
            LEFT = a*pow(3,qleft,mod)
        if qright > 0:
            RIGHT = c*pow(3,qright,mod) + qright*pow(3,qright-1,mod)
        else:
            RIGHT = c*pow(3,qright,mod)
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*(10**i))%2019
        dp[x%2019] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,2019))%2019
        dp[x] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

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

n, m = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
for r in info:
	if r[0] == 1:
		q.append(r[1])

	elif (r[0] in q) and r[1] == n:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
side1 = set()
side2 = set()

for i in range(m):
	a, b = map(int, input().split())

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")
### BUGGY CODE ###

s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        index.sort()
        for jj in index:
            if prev < jj:
                ans+= jj-prev
                prev = jj
                break
        else:
            ans += (ls-prev)+index[0]
            prev = index[0]

print(ans)



### FIXED CODE ###

s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

from bisect import bisect_right

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        nex = bisect_right(index, prev)
        if nex == len(index):
            ans += (ls-prev)+index[0]
            prev = index[0]
        else:
            ans+= index[nex]-prev
            prev = index[nex]

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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, a: "List[int]"):
    a.sort(reverse=True)
    dp = [False] * K
    dp[0] = True
    ret = 0
    for i in range(N):
        for j in range(K - 1, -1, -1):
            if dp[j]:
                if j + a[i] >= K:
                    ret = i + 1
                else:
                    dp[j + a[i]] = True
    print(N - ret)
    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
    K = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, a: "List[int]"):
    a.sort(reverse=True)
    dp = [False] * K
    dp[0] = True
    ret = 0
    for i in range(N):
        for j in range(K - 1, -1, -1):
            if dp[j]:
                if j + a[i] >= K:
                    ret = i + 1
                else:
                    dp[j + a[i]] = True
    print(N - ret)
    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
    K = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, a)

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

import sys
input = sys.stdin.readline
r,c,K=map(int, input().split())
grid=[[0]*(c+1) for _ in range(r+1)]
for i in range(K):
    ri,ci,vi=map(int, input().split())
    grid[ri][ci]=vi

dp=[[[0]*4 for _ in range(c+1)] for _ in range(r+1)]

for i in range(1,r+1):
    for j in range(1,c+1):
        dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j]))
        if grid[i][j]==0:
            for k in range(4):
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
        if grid[i][j]!=0:
            dp[i][j][0]=max(dp[i][j][0],dp[i][j-1][0])
            dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j])+grid[i][j])
            for k in range(1,4):
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+grid[i][j],dp[i][j-1][k])

print(max(dp[-1][-1]))

### FIXED CODE ###

R,C,K = map(int,input().split())

grid=[[0]*C for _ in range(R)]
for i in range(K):
    x,y,v = map(int,input().split())
    grid[x-1][y-1] = v
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]

for i in range(R):
    for j in range(C):
        dp1[i][j] = max(dp1[i][j-1],dp1[i-1][j]+grid[i][j],
                    dp2[i-1][j]+grid[i][j],dp3[i-1][j]+grid[i][j])
        dp2[i][j] = max(dp2[i][j-1],dp1[i][j-1]+grid[i][j])
        dp3[i][j] = max(dp3[i][j-1],dp2[i][j-1]+grid[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 = int(input())
arr = list(map(int, input().split()))
check = [1 for _ in range(n)]
for i in range(n):
    if check[i] == 1:
        for j in range(n):
            if i != j:
                if arr[i] % arr[j] == 0:
                    check[i] = 0
                if arr[j] % arr[i] == 0:
                    check[j] = 0
print(check.count(1))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(1, n):
    if arr[i] == arr[i-1]:
        ap[arr[i]] = 1
        
for i in range(n):
    if not ap[arr[i]]:
        count += 1
    if i == 0 or arr[i] != arr[i-1]:
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
tizu = [list(input()) for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = 0

queue = deque()
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "#":
            queue.append([i, j])
            queue.append(0)
            check[i][j] = True

direct = [[1, 0], [-1, 0], [0, 1], [0, -1]]        
while queue:
    pos = queue.popleft()
    cnt = queue.popleft()
    for dy, dx in direct:
        n_y = pos[0] + dy
        n_x = pos[1] + dx
        if n_y == -1 or n_y == h or n_x == -1 or n_x == w:
            continue
        if check[n_y][n_x]:
            continue
        check[n_y][n_x] = True
        ans = max(ans, cnt + 1)
        queue.append([n_y, n_x])
        queue.append(cnt + 1)
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
tizu = [list(input()) for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
queue = deque()
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "#":
            queue.append([i, j])
            queue.append(0)
            check[i][j] = True
            
while queue:
    pos = queue.popleft()
    ans = queue.popleft() + 1
    for dy, dx in directions:
        next_y = pos[0] + dy
        next_x = pos[1] + dx
        if next_x == -1 or next_y == -1 or next_x == w or next_y == h:
            continue
        if check[next_y][next_x]:
            continue
        check[next_y][next_x] = True
        queue.append([next_y, next_x])
        queue.append(ans)
        
print(ans - 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip() for _ in range(n)]
new = []
for i in range(n):
    sort = sorted(data[i])
    sorting = "".join(sort)
    new.append(sorting)
new.sort()
score = 0
news = list(set(new))
for s in range(len(news)):
    k = new.count(news[s])
    score += int((k-1)*k/2)
print(score)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip() for _ in range(n)]
new = []
for i in range(n):
    sort = sorted(data[i])
    sorting = "".join(sort)
    new.append(sorting)
new.sort()
score = 0
s = 0
count  = 0
while s<n-1:
    daburi = 1
    for p in range(s,n-1):
        if new[p] == new[p+1]:
            daburi += 1
        else:
            break
    score += daburi*(daburi-1)//2
    count += daburi
    s = count
print(score)
### BUGGY CODE ###

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

i_plus_Ai = [0 for i in range(N)]
dict = {}
for i in range(N):
    i_plus_Ai[i] = i + As[i]
    tmp = i - As[i]
    if tmp not in dict:
        dict[tmp] = [i]
    else:
        dict[tmp].append(i)
    dict[tmp].sort()

count = 0
for i in range(N):
    if i_plus_Ai[i] in dict:
        kouho = dict[i_plus_Ai[i]]
        for j in range(len(kouho)):
            if kouho[j] > i:
                count += len(kouho) - j
                break

print(count)


### FIXED CODE ###

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

i_plus_Ai = [0 for i in range(N)]
dict = {}
for i in range(N):
    i_plus_Ai[i] = i + As[i]
    tmp = i - As[i]
    if tmp not in dict:
        dict[tmp] = [i]
    else:
        dict[tmp].append(i)

count = 0
for i in range(N):
    if i_plus_Ai[i] in dict:
        kouho = dict[i_plus_Ai[i]]
        for j in range(len(kouho)):
            if kouho[j] > i:
                count += len(kouho) - j
                break

print(count)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    N=len(S)
    A=[1]*N
    for _ in range(N):
        for i in range(N-1):
            if S[i]=='R' and S[i+1]=='R':
                A[i+2]+=A[i]
                A[i]=0
        for i in range(N-1,0,-1):
            if S[i]=='L' and S[i-1]=='L':
                A[i-2]+=A[i]
                A[i]=0
    print(*A)




resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    N = len(S)
    A = [1] * N
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] == 'R':
            A[i + 2] += A[i]
            A[i] = 0
    for i in range(N - 1, 0, -1):
        if S[i] == 'L' and S[i - 1] == 'L':
            A[i - 2] += A[i]
            A[i] = 0
    print(*A)


resolve()
### BUGGY CODE ###

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

if 0 in aa:
    print("0")
else:
    result = 1
    for a in aa:
        result *= a

    if result > pow(10, 18):
        result = -1

    print(result)


### FIXED CODE ###

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

if 0 in aa:
    print('0')
    exit(0)

result = 1
for a in aa:
    result *= a
    if result > pow(10, 18):
        print('-1')
        exit(0)

print(result)
### BUGGY CODE ###

import sys
import numpy as np
import numba
from numba import jit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@jit
def main(p):
  count = 0
  if np.any(p%2==1):
    return 0
  if np.unique(p).size == 1:
    return -1
  while True:
    if np.any(p%2 == 1):
      return count
    p[0] = p[1]/2 + p[2]/2
    p[1] = p[0]/2 + p[2]/2
    p[2] = p[0]/2 + p[1]/2
    count += 1


p = np.array(readline().split(), np.int64)
print(main(p))

### FIXED CODE ###

a, b, c = map(int, input().split())
if a == b and b == c:
    if a % 2 == 0:
        print(-1)
    else:
        print(0)
else:
    count = 0
    while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
        a, b, c = (b + c) // 2, (c + a) // 2, (a + b) // 2
        count += 1
    print(count)
### BUGGY CODE ###

class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def dump(self):
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                print str(n['key']),
                n = n['next']
        print


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

l.dump()

### FIXED CODE ###

class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def dump(self):
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                print str(n['key']),
                n = n['next']
        print


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())
commands = []
for i in range(n):
    commands.append(raw_input())

l = DoublyLinkedList()
for c in commands:
    a = c[6]
    if a == "F":
        l.deleteFirst()
    elif a == "L":
        l.deleteLast()
    else:
        val = int(c[7:])
        op = c[0]
        if op == "i":
            l.insert(val)
        else:
            l.delete(val)

l.dump()
### BUGGY CODE ###

data = []

i = input()

for n in range(int(i)):
	data.append(int(input()))

for i in range(len(data)):
	print(max(data[0:i]+data[i+1:]))

### FIXED CODE ###

import copy

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
data2 = copy.copy(data)
data2.remove(maxInt)
max2Int = max(data2)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max2Int)
### BUGGY CODE ###

import numpy as np
N = int(input())
L = np.array(list(map(int, input().split())))

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if (L[j] - L[i] < L[k]) & (L[k] < L[j] + L[i]):
                ans += 1
            elif L[j] + L[i] < L[k]:
                break

print(ans)


### FIXED CODE ###

import bisect

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

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        index = bisect.bisect_right(L, L[i] + L[j]-1)
        ans += index - j - 1

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

n,p=map(int,input().split())
S=input()
M={0:1}
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    for i in range(n):
        s=int(S[(n-1-i):]) #右からi+1桁取り出す
        r=s%p #剰余
        if r in M: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
            M[r]+=1
        else: #なかったら追加
            M[r]=1
print(ans)

### FIXED CODE ###

n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    cnt=10%p #10の累乗の剰余を記録しておく
    for i in range(n):
        s=int(S[n-1-i]) #右からi+1桁目を取り出す
        if i==0:
            r=s%p #剰余
        else:
            r=(cnt*s+r)%p #前の剰余にs*cntをたす
            cnt=cnt*10%p #更新
        if M[r]>=1: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
        M[r]+=1

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

import math

print(math.log10(2**5000000000000000))

### FIXED CODE ###

s = list(str(input()))
k = int(input())
ans = '1'

for i in range(k):
  if s[i] != '1':
    ans = s[i]
    break
  if len(s)-1 == i:
    break
    
print(int(ans))
### BUGGY CODE ###

# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
P = LF()

# dp[i][j]: i番目のコインまで投げた時，j枚のコインが表になる確率
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1

# 調和級数
# O(NlogN)
for i in range(n):
    for j in range(i + 1):
        if dp[i][j] == 0:
            continue
        # P[i]が裏
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
        # P[i]が表
        dp[i + 1][j + 1] += dp[i][j] * P[i]

print(sum(dp[n][n // 2 + 1:]))


### FIXED CODE ###

# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
P = LF()

# dp[i][j]: i番目のコインまで投げた時，j枚のコインが表になる確率
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1

# 調和級数
# O(NlogN)
for i in range(n):
    for j in range(i + 1):
        if dp[i][j] == 0:
            continue
        # P[i]が裏
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
        # P[i]が表
        dp[i + 1][j + 1] += dp[i][j] * P[i]

print(sum(dp[n][n // 2 + 1:]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

cnt = 0
ans = 0
while cnt < M:
    min_cost = min(A)
    min_index = A.index(min_cost)
    amount = B[min_index]
    if cnt + amount <= M:
        ans += min_cost * amount
        cnt += amount
    else:
        ans += min_cost * (M - cnt)
        break
    A = [A[i] for i in range(len(A)) if i != min_index]
    B = [B[i] for i in range(len(B)) if i != min_index]
    
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

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

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

for i in range(N):
    C = sorted([x for index, x in enumerate(X) if index != i])
    print(C[len(C)//2])


### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
CL = Y[N//2-1]
CR = Y[N//2]

for x in X:
    if x < CR:
        print(CR)
    else:
        print(CL)