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

#!/usr/bin/env pypy3

import itertools


UNDEF = 0


def mex(s):
    for i in itertools.count(1):
        if i not in s:
            return i


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF for _ in range(n - 1)]
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        while len(cur_cols) < num_adj:
            nc = mex(cur_cols)
            cur_cols.add(nc)
            new_cols.add(nc)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3

import itertools


UNDEF = 0


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF] * (n - 1)
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        for i in itertools.count(1):
            if len(cur_cols) + len(new_cols) >= num_adj:
                break
            elif i not in cur_cols:
                new_cols.add(i)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


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

a,b=map(int,input().split())
if (a+b)%2 != 0:
  print('IMPOSSIBLE')
else:
  for i in range(max(a,b)):
    if abs(a-i) == abs(b-i):
      print(i)

### FIXED CODE ###

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

if (a + b)%2 ==0:
    print((a+b)//2)
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

from bisect import bisect_left
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = [-1]
    for c in range(W):
        if s[r][c] == '#':
            t.append(c)
    t.append(W)
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = [-1]
    for r in range(H):
        if s[r][c] == '#':
            t.append(r)
    t.append(H)
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = -1
        ri = bisect_left(row_blocks[r], c)
        t += (row_blocks[r][ri] - 1) - row_blocks[r][ri - 1]
        ci = bisect_left(col_blocks[c], r)
        # print(r, c, ri, ci, col_blocks[c])
        t += (col_blocks[c][ci] - 1) - col_blocks[c][ci - 1]
        ans = max(ans, t)
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = []
    x = 0
    for c in range(W):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(W - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = []
    x = 0
    for r in range(H):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(H - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = row_blocks[r][c] + col_blocks[c][r] - 1
        ans = max(ans, t)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary = sorted(ary)
a = ary.index(0)
ans = float("Inf")
for i in range(N + 1):
    if i == a: continue

    k = abs(i - a)
    d = abs(ary[i])
    if k >= K and ans > d:
        ans = d
    if i < a:
        k = K - abs(i - a)
        d = abs(ary[i])
        if 0 < k < len(ary[a:]):
            d += abs(ary[i] - ary[k + a])
            if ans > d:
                ans = d

print(0 if ans == float("Inf") else ans)


### FIXED CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary.sort()
zero = ary.index(0)
a = [abs(i - zero) for i in range(N + 1)]
ary.pop(zero)
ans = float("Inf")
for i in range(N - K + 1):
    b = N - i - 1
    d = abs(ary[i])
    if a[i] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[i] - ary[i + K - 1]))
    d = abs(ary[b])
    if a[b] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[b] - ary[b - K + 1]))
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
gcds=[]

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

for i in range(len(l)):
    omitlist=list(l)
    omitlist.pop(i)
    n=len(omitlist)

    if n==1:
        gcds.append(omitlist[0])
    else:
        element = gcd(omitlist[0], omitlist[1])
        if n==2:
            gcds.append(element)
        else:
            for i in range(2,n):
                element=gcd(element,omitlist[i])
            gcds.append(element)

print(max(gcds))

### FIXED CODE ###

n=int(input())
left=list(map(int,input().split()))
right=list(left)
right.reverse()
gcds=[]
gcdleft=[]
gcdright=[]

gcdleft.append(left[0])
gcdright.append(right[0])

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

if n==2:
    gcds.append(gcdleft[0])
    gcds.append(gcdright[0])
else:
    for i in range(1,n-1):
        gcdleft.append(gcd(gcdleft[i-1],left[i]))
        gcdright.append(gcd(gcdright[i-1],right[i]))
    gcds.append(gcdright[-1])
    for i in range(0,n-2):
    	gcds.append(gcd(gcdleft[i],gcdright[n-3-i]))
    gcds.append(gcdleft[-1])

print(max(gcds))
### BUGGY CODE ###

#!/usr/bin/env python3

# input
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [-1 for _ in range(q)]
c = [-1 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

def innerproduct(d):
    ans = 0
    for key, value in d.items():
        ans += int(key)*int(value)
    return ans

# calc
d = {}
for i in a:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1

# print(d)
ans = sum(a)
for i in range(q):
    if b[i] in d:
        # ans -= b[i]*d[b[i]]
        if c[i] not in d:
            d[c[i]] = d[b[i]]
        else:
            d[c[i]] += d[b[i]]
        # tmp = d[b[i]]
        d[b[i]] = 0
        # ans += tmp*d[c[i]]

    #print(d)
    print(innerproduct(d))

### FIXED CODE ###

#!/usr/bin/env python3

# input
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [-1 for _ in range(q)]
c = [-1 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

def innerproduct(d):
    ans = 0
    for key, value in d.items():
        ans += int(key)*int(value)
    return ans

# calc
d = {}
for i in a:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1

# print(d)
ans = sum(a)
for i in range(q):
    if b[i] in d:
        ans -= b[i]*d[b[i]]
        tmp = d[b[i]]
        if c[i] not in d:
            d[c[i]] = d[b[i]]
        else:
            d[c[i]] += d[b[i]]
        d[b[i]] = 0
        ans += tmp*c[i]

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

n = int(input())
a = list(map(int, input().split()))
s = [0]
b = c = 0
i = j = 0

for i in range(n):
    s.append(s[i] + a[i])
s.sort()

for i in set(s):
    for j in s:
        if i == j:
            b += 1
    c += int(b*(b-1)/2)
    b = 0

print(c)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
b = 1
c = 0

for i in range(n):
    s.append(s[i] + a[i])
s.sort()
s.append('\0')

for i in range(1, len(s)):
    if s[i] == s[i-1]:
        b += 1
        continue
    c += int(b*(b-1)/2)
    b = 1
print(c)
### BUGGY CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//3
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
while G[0]<t:
    G.insert(0,G[0]*3+1)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])

### FIXED CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//5
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
#Gt=[4, 9, 20, 46, 103, 233, 525, 1182,2660, 5985, 13467]
f=1.0
while f<t:
    f*=2.2
    f=int(f)
    G.insert(0,f)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])
### BUGGY CODE ###

def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False
    i = 3
    xx = int(pow(x, 0.5))
    while i <= xx:
        if x % i == 0:
            return False
        i += 2
    return True

n = int(input())
rx = int(pow(n, 0.5))
l = rx+1
ps = []
for i in range(n):
    if isPrime(i):
        ps.append(i)
ans = []
i = 0
nn = n
ps.append(nn)
while n != 1:
    if n % ps[i] == 0:
        n //= ps[i]
        ans.append(ps[i])
    else:
        i += 1
print(str(nn)+":", ' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
print("{}:".format(n), end='')
x = int(pow(n, 0.5))+1
for i in range(2, x):
    while n % i == 0:
        print(" {}".format(i), end='')
        n //= i
print(' {}'.format(n) if n != 1 else '')
### BUGGY CODE ###

#ABC164d
s = str(input())
S = int(s)
s = list(s)

for i in range(len(s)):
    s[i] = int(s[i])

ans = 0
T = 0

for i in range(len(s)):
    for j in range(i,len(s)):
        t = s[i:j+1]
        for i2 in range(len(t)):
            T += t[i2] * 10**(len(t)-1-i2)
        if T%2019==0 and T != 0:
            ans += 1
        T = 0
print(ans)


### FIXED CODE ###

#ABC164d
def main():
    s = input()
    MOD = 2019
    d = [ 0 for i in range(MOD)]
    # print(d)
    ans = 0
    k = 0
    d[0] = 1
    s = s[::-1]
    # print(s)
    p = 1
    for i in s:
        # print(p,i,k)
        # print('pnosiki')
        # print(p * int(i) + k)
        k = (p * int(i) + k) % MOD
        # print('k:')
        # print(k)
        ans += d[k]
        d[k] += 1
        p = (p * 10) % MOD
    print(ans)
    return

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

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

dp = [10**9] * N # DPテーブルの作成
dp[0] = 0

for i in range(1,N):
    for j in range(K+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+abs(h_list[i] - h_list[i-j]))
    #print(dp)
print(dp[N-1])


### FIXED CODE ###

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

dp = [10**9] * N # DPテーブルの作成
dp[0] = 0

for i in range(1,N):
    for j in range(K+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j]+abs(h_list[i] - h_list[i-j]))
    #print(dp)
print(dp[N-1])
### BUGGY CODE ###

import collections

n = int(input())
participant = list(map(int, input().split()))
hashSet = collections.defaultdict(lambda:set())
for i,v in enumerate(participant):
  hashSet[v].add(i)
  
ans = 0
for i,v in enumerate(participant):
  for key, s in hashSet.items():
    if i+v+key in s:
      ans += 1

print(ans)

### FIXED CODE ###

import collections
 
input()
p = list(map(int, input().split()))
map1 = collections.defaultdict(lambda:0)
map2 = collections.defaultdict(lambda:0)
 
for i, v in enumerate(p):
  map1[i+v] += 1
  map2[i-v] += 1

ans = 0
for i in map1:
  if i in map2:
    ans += map1[i] * map2[i]

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

S = input()

MOD = 1000000007

As = []
Bs = []
Cs = []
S_length = len(S)
hatena_count = 0
for i, c in enumerate(S):
    # 'A':0, 'B':1, 'C':2
    if c == 'A':
        As.append([S_length - i, 3])
    elif c == 'B':
        Bs.append([S_length - i, 3])
    elif c == 'C':
        Cs.append([S_length - i, 3])
    elif c == '?':
        hatena_count += 1
        As.append([S_length - i, 1])
        Bs.append([S_length - i, 1])
        Cs.append([S_length - i, 1])

new_Bs = []
for b in Bs:
    new_Bs.append([b, sum([c[1] for c in Cs if b[0] > c[0]])])

count = 0
for a in As:
    count += 3**(hatena_count - 3) * a[1] * sum([b[0][1] * b[1] for b in new_Bs if a[0] > b[0][0]])

print(int(count % MOD))

### FIXED CODE ###

S = input()

MOD = 1000000007

# a_b_c, a_b_hc, a_hb_c, a_hb_hc, ha_b_c, ha_b_hc, ha_hb_c, ha_hb_hc
count = [[0, 0, 0] for _ in range(8)]
hatena_count = 0

for c in S:
    if c == 'A':
        nums = [0,1,2,3]
        for num in nums:
            count[num][0] += 1
    elif c == 'B':
        nums = [0,1,4,5]
        for num in nums:
            count[num][1] += count[num][0]
    elif c == 'C':
        nums = [0,2,4,6]
        for num in nums:
            count[num][2] += count[num][1]
    elif c == '?':
        # hc
        nums = [1,3,5,7]
        for num in nums:
            count[num][2] += count[num][1]
        
        # hb
        nums = [2,3,6,7]
        for num in nums:
            count[num][1] += count[num][0]

        # ha
        nums = [4,5,6,7]
        for num in nums:
            count[num][0] += 1
        
        hatena_count += 1

total = 0
coef = [0, 1, 1, 2, 1, 2, 2, 3]
for i in range(8):
    total += count[i][2] * 3**(hatena_count - coef[i])

print(int(total % MOD))
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

uf = UnionFind(n)
for x,y in xy:
    uf.union(x,y)

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        costs.append(a[mem])
    costs.sort()
    ans+=costs[0]
    all_costs.extend(costs[1:])

all_costs.sort()
ans+=sum(all_costs[:(g-2)])

print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

uf = UnionFind(n)
for x,y in xy:
    uf.union(x,y)

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0
all_costs=[]

from collections import defaultdict
costs=defaultdict(list)
for i in range(n):
    costs[uf.find(i)].append(a[i])

for k,v in costs.items():
    v.sort()
    ans+=v[0]
    all_costs.extend(v[1:])

all_costs.sort()
ans+=sum(all_costs[:(g-2)])

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

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

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

S = input()
stack = []
ans = 0
for ch in S:
    if len(stack) == 0 or stack[-1] == ch:
        stack.append(ch)
    else:
        ans += 2
        stack = stack[:-1]
print(ans)




### FIXED CODE ###

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

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

S = input()
stack = []
ans = 0
for ch in S:
    if len(stack) == 0 or stack[-1] == ch:
        stack.append(ch)
    else:
        ans += 2
        # stack = stack[:-1]  # 遅い??
        del stack[-1]
print(ans)
### BUGGY CODE ###

s = input()[::-1]
keys = ["dream", "dreamer", "erase", "eraser"]
keys_ = [i[::-1] for i in keys]
i = 0
t = ''

while(i < len(s)):
  for key in keys_:
    if s[i:].startswith(key):
      t += key
      i += len(key)
    if t == s:
      print('YES')
      exit()
    else:
      continue
else:
  print(t)
  print('NO')

### FIXED CODE ###

s = input()[::-1]
keys = ["dream", "dreamer", "erase", "eraser"]
keys_ = [i[::-1] for i in keys]
i = 0
t = ''

for _ in range(len(s)):
  for key in keys_:
    if s[i:].startswith(key):
      t += key
      i += len(key)
    if t == s:
      print('YES')
      exit()
else:
  print('NO')
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
mod=998244353

#階乗テーブル
g1=[1,1]
for i in range(2,3*M//2+N+2):
    g1.append(g1[-1]*i%mod)

def cmb(n,r):
    return g1[n]*pow(g1[r],mod-2,mod)*pow(g1[n-r],mod-2,mod)%mod

#奇数の和で場合分け
#iは奇数の数

ans=0
for i in range(min(N+1,M+1)):
    if M%2!=i%2:
        continue
    m=(3*M-i)//2
    num=(cmb(m+N-1,N-1)-i*cmb(m-M+N-1,N-1))%mod
    if m>=M+1:
        num=(num-(N-i)*cmb(m-M+N-2,N-1))%mod
    ans=(ans+cmb(N,i)*num)%mod

print(ans)   

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
mod=998244353

inv=[0]*(3*M//2+N+2)
inv[1]=1
for i in range(2,3*M//2+N+2):
    inv[i]=-(mod//i)*inv[mod%i]%mod

#階乗テーブル
g1=[1,1]
g2=[1,1]
for i in range(2,3*M//2+N+2):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(g2[-1]*inv[i]%mod)
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

#奇数の和で場合分け
#iは奇数の数

ans=0
for i in range(min(N+1,M+1)):
    if M%2!=i%2:
        continue
    m=(3*M-i)//2
    num=(cmb(m+N-1,N-1)-i*cmb(m-M+N-1,N-1))%mod
    if m>=M+1:
        num=(num-(N-i)*cmb(m-M+N-2,N-1))%mod
    ans=(ans+cmb(N,i)*num)%mod

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

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

sum = 0
A.sort(reverse=False)

for i in range(N):
    for j in range(N-(i+1)):
        sum += A[i]*A[j+i+1]

print(sum%((10**9)+7))


### FIXED CODE ###


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


mod = 10**9+7
s = sum(A)

ans = 0

for i in range(n):
    s -= A[i]
    ans += (A[i] * s) % mod

print(ans%mod)
### BUGGY CODE ###

n = int(input())
c = []
for _ in range(n):
    c.append(list(map(int,input().split())))

ans = 0
a = 100000000000000
m = 0
lm = 0
rm = 0
lt  = []
rt  = []
lb = []
rb = []

for l in c:
    m = max(m,l[0]+l[1])
    a = min(a,l[0]+l[1])
    if l[0] > l[1]:
        rm = max(rm,l[0]-l[1])
    if l[0] < l[1]:
        lm = max(lm,l[1]-l[0])

for l in c:
    if l[0] + l[1] == m:
        rt.append(l)
    if l[0] + l[1] == a:
        lb.append(l)
    if l[0] > l[1] and l[0] - l[1] == rm:
        rb.append(l)
    if l[0] < l[1] and l[1] - l[0] == lm:
        lt.append(l)


for i in lt:
    for j in rb:
        ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))

for i in rt:
    for j in lb:
        ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))
print(ans)




### FIXED CODE ###

n = int(input())
c = []
for _ in range(n):
    c.append(list(map(int,input().split())))

ans = 0
a = 100000000000000
m = 0
lm = 0
rm = 0
lt  = []
rt  = []
lb = []
rb = []

for l in c:
    m = max(m,l[0]+l[1])
    a = min(a,l[0]+l[1])
    if l[0] > l[1]:
        rm = max(rm,l[0]-l[1])
    if l[0] < l[1]:
        lm = max(lm,l[1]-l[0])

for l in c:
    if l[0] + l[1] == m:
        rt.append(l)
    if l[0] + l[1] == a:
        lb.append(l)
    if l[0] > l[1] and l[0] - l[1] == rm:
        rb.append(l)
    if l[0] < l[1] and l[1] - l[0] == lm:
        lt.append(l)


if len(lt)>0 and len(rb) > 0:
    i = lt[0]
    j = rb[0]
    ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))

if len(rt)>0 and len(lb) > 0:
    i = rt[0]
    j = lb[0]
    ans = max(ans,abs(i[0]-j[0])+abs(i[1]-j[1]))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

N = I()
p = [float(x) for x in input().split()]

dp = FILL(0,N+1,N+1)
dp[0][0] = 1
dp[0][1] = 0
for i in range(N):
    for f in range(i+2):
        if f == 0:
            dp[i+1][f] = dp[i][f]*(1-p[i])
        else:
            dp[i+1][f] = dp[i][f]*(1-p[i]) + dp[i][f-1]*p[i]
ans = 0
for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
P = list(map(float,input().split()))
dp = FILL2(0,N+3,N+3)
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*P[i]
        dp[i+1][j] += dp[i][j]*(1-P[i])
print(sum(dp[N][N//2+1:]))