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

a, b = map(int, input().split())
l = []
t = 0
i = 1
while i <= 999:
  t += i
  l.append(t)
  i += 1

def f():
  for i in range(1, 499500):
    for j in range(len(l)-1):
      if a + i == l[j] and b + i == l[j+1]:
        return i

print(f())

### FIXED CODE ###

a, b = map(int, input().split())
diff = b - a
b_2 = (diff + 1) * diff // 2
print(b_2 - b)
### BUGGY CODE ###

s=str(input())
ans = 0
for i in range(len(s)-4):
  for j in range(i+4,len(s)+1):
    if int(s[i:j]) % 2019 == 0:
      ans += 1
print(ans)


### FIXED CODE ###

s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
ans = 0
num = 0
k = 1

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10
  k %= 2019
for i in dp:
  ans += i*(i-1)/2

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

import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N, K = map(int, input().split())
    H = [0] + list(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF for _ in range(N + 1)]
    dp[1] = 0
    for i in range(1, N):
        for k in range(1, K + 1):
            if i + k <= N:
                tmp = dp[i] + abs(H[i + k] - H[i])
                if dp[i + k] > tmp:
                    dp[i + k] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N, K = map(int, input().split())
    H = [0] + list(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF for _ in range(N + 1)]
    dp[1] = 0
    for i in range(1, N):
        for k in range(1, K + 1):
            if i + k <= N:
                tmp = dp[i] + abs(H[i + k] - H[i])
                if dp[i + k] > tmp:
                    dp[i + k] = tmp

    print(dp[-1])


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

A,B,C,D=map(int,input().split())
a={i for i in range(A,B+1)}
b=set()
c=set()
for i in range(A,B+1):
  if i%C==0:
    b.add(i)
  
for i in range(A,B+1):
  if i%D==0:
    c.add(i)
print(len(a-b-c))


### FIXED CODE ###

A,B,C,D=map(int,input().split())

def unko(x,C,D):
  import fractions
  t=int(fractions.gcd(C,D))
  t_=C*D//t
  return x-(x//C+x//D-x//t_)
print(int(unko(B,C,D)-unko(A-1,C,D)))
### BUGGY CODE ###

from heapq import heapify, heappushpop

X, Y, A, B, C = map(int, input().split())
# 大きい順にソートして受け取っておく
p = sorted(list(map(int, input().split())))[::-1]
q = sorted(list(map(int, input().split())))[::-1]
r = sorted(list(map(int, input().split())))[::-1]
ans_list = p[:X] + q[:Y]  # 着色しない場合
heapify(ans_list)
m = min(ans_list)
for ri in r:
    if ri > m:
        heappushpop(ans_list, ri)
        m = min(ans_list)
    else:
        break
print(sum(ans_list))


### FIXED CODE ###

from heapq import heapify, heappushpop

X, Y, A, B, C = map(int, input().split())
# 大きい順にソートして受け取っておく
p = sorted(list(map(int, input().split())))[::-1]
q = sorted(list(map(int, input().split())))[::-1]
r = sorted(list(map(int, input().split())))[::-1]
ans_list = p[:X] + q[:Y]  # 着色しない場合
heapify(ans_list)
for ri in r:
    if ri > ans_list[0]:
        heappushpop(ans_list, ri)
    else:
        break
print(sum(ans_list))
### BUGGY CODE ###

mod = 10**9+7

def f(n,k,p):
    n1, k = n+1, min(k, n-k)
    numer = denom = 1
    for i in range(1,k+1):
        numer = numer*(n1-i)
        denom = denom*i
    return numer*pow(denom,p-2,p)%p

r1,c1,r2,c2 = map(int,input().split(" "))
ans = f(r2+c2+2,c2+1,mod)-f(r2+c1+1,c1,mod)-f(r1+c2+1,c2+1,mod)+f(r1+c1,c1,mod)
print(ans%mod)

### FIXED CODE ###

mod = 10**9+7

f = [1]*(2*10**6+5)
f[0] = 1
for i in range(1,2*10**6+4):
    f[i] = f[i-1]*i%mod

def inv(i):
    return pow(f[i],mod-2,mod)

def g(x,y):
    return f[x+y]*inv(x)*inv(y)%mod

r1,c1,r2,c2 = map(int,input().split(" "))
ans = g(r2+1,c2+1)-g(r2+1,c1)-g(r1,c2+1)+g(r1,c1)
print(ans%mod)
### BUGGY CODE ###

import sys

i1 = input().split(' ')
a=int(i1[0])
b=int(i1[1])

r = 0
if a>b:
  r=a
else:
  r=b

aa = abs(a)
ba = abs(b)

for i in range(r):
  aa = abs(a-i)
  ba = abs(b-i)
  if aa==ba:
    print(i)
    sys.exit()

print("IMPOSSIBLE")


### FIXED CODE ###

i1 = input().split(' ')
a=int(i1[0])
b=int(i1[1])

aa = abs(a)+abs(b)
if aa%2 == 0:
  print(int(aa/2))
  exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(n, m + 1):
    if m % i == 0:
        print(m // i)
        exit()

### FIXED CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, int(m ** .5) + 1):
    if m % i == 0:
        b = m // i
        if i * n <= m:
            ans = max(ans, i)
        if b * n <= m:
            ans = max(ans, b)
print(ans)
### BUGGY CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)
l = range(mean,maxinp)



if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP):
            print(maxP)
            break

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
a = [abs(p[0])+abs(p[1]) for p in x]
t = max(a)
b = [q%2 for q in a]
if len(set(b)) != 1:
    print(-1)
    exit()
print(t)
for i in range(t):
    print("1 ", end="")
print()
for i in range(n):
    ch1 = ch2 = ""
    if x[i][0] >= 0:
        ch1 = "R"
    else:
        ch1 = "L"
    if x[i][1] >= 0:
        ch2 = "U"
    else:
        ch2 = "D"
    for j in range((t-a[i])//2):
        print("RL", end="")
    for j in range(abs(x[i][0])):
        print(ch1, end="")
    for j in range(abs(x[i][1])):
        print(ch2, end="")
    print()



### FIXED CODE ###

n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
mod = sum(XY[0])%2
for x, y in XY:
    if mod != (x+y)%2:
        print(-1)
        exit()

m = 33-mod
print(m)
D = [2**i for i in range(31, -1, -1)]
if mod == 0:
    D.append(1)

print(" ".join(map(str, D)))
for x, y in XY:
    w = " "
    for d in D:
        if x-y >= 0 and x+y >= 0:
            w += "R"
            x -= d
        elif x-y < 0 and x+y >= 0:
            w += "U"
            y -= d
        elif x-y >= 0 and x+y < 0:
            w += "D"
            y += d
        else:
            w += "L"
            x += d
    print(w)
### BUGGY CODE ###

def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    ans = 0
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        if ans < min(i,j):
            ans = min(i,j)
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            if ans < min(i+k,a[k]):
                ans = min(i+l,a[k])
            k+=1

        i +=k
        j -=k
    return ans
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a = z_argorithm(s[i:])
        if ans < a:
            ans = a
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>=R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
        elif z[i-L]<R-i: # 過去の結果が全て使える
            z[i]=z[i-L]
        else: # 過去の結果が一部使える
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

for i in range(2, N + 1):
    m = (10 ** (i - 1)) % 13
    for j in range(13):
        if S[-i] == '?':
            for k in range(10):
                d = k * m % 13
                dp[i][j] += dp[i - 1][(13 + j - d) % 13]
        else:
            d = int(S[-i]) * m
            dp[i][j] += dp[i - 1][(13 + j - d) % 13]
        dp[i][j] %= MOD

print(dp[N][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

m = 1
for i in range(2, N + 1):
    m = m * 10 % 13
    for j in range(13):
        num = '?' if S[-i] == '?' else int(S[-i])
        for k in range(10):
            if num == '?' or k == num:
                d = k * m % 13
                dp[i][j] = (dp[i][j] + dp[i - 1][(13 + j - d) % 13]) % MOD

print(dp[N][5])
### BUGGY CODE ###

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for i in range(0, N):
        j = i + 1
        c = Es.count(j)
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)


### FIXED CODE ###

from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)
### BUGGY CODE ###

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

while M>0:
    max_A = max(A)
    ind = A.index(max_A)
    A[ind] = A[ind]//2
    M = M-1
print(sum(A))

### FIXED CODE ###

import heapq
N, M = list(map(int, input().split()))
A = [-a for a in list(map(int, input().split()))]
heapq.heapify(A)

while M>0:
    max_a = heapq.heappop(A)
    heapq.heappush(A,-int(-max_a/2))
    M = M-1
print(-sum(A))
### BUGGY CODE ###

s = str(input())
n = int(input())
q_list = [list(map(str, input().strip().split())) for i in range(n)]

rev = 0
for_s = ''
rev_s = ''

out = ''
out += s
for q in q_list:
    if q[0] == '1':
        rev = 1 - rev
    elif q[1] == '1':
        if rev == 0:
            #rev_s += q[2]
            out = q[2] + out
        else:
            #for_s += q[2]
            out = out + q[2]
    else:
        if rev == 0:
            #for_s += q[2]
            out = out + q[2]
        else:
            #rev_s += q[2]
            out = q[2] + out

#if rev == 0:
#    out = rev_s[::-1] + s + for_s
#else:
#    out = for_s[::-1] + s + rev_s
if rev == 1:
    out = out[::-1]
print(out)

### FIXED CODE ###

s = str(input())
n = int(input())
q_list = [list(map(str, input().strip().split())) for i in range(n)]

rev = 0
for_s = ''
rev_s = ''

out = ''
for q in q_list:
    if q[0] == '1':
        rev = 1 - rev
    elif q[1] == '1':
        if rev == 0:
            rev_s += q[2]
        else:
            for_s += q[2]
    else:
        if rev == 0:
            for_s += q[2]
        else:
            rev_s += q[2]

if rev == 0:
    out = rev_s[::-1] + s + for_s
else:
    out = for_s[::-1] + s[::-1] + rev_s
print(out)
### BUGGY CODE ###

n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
dp=[[0 for i in range(0,n+1)]for j in range(n+1)]

dp[0][0]=1.0
# for i in range(1,n+1):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

k=(n//2)+1
ans=0.0
for i in range(k,n+1):
    ans+=dp[n][i]
print(ans)




### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
dp=[[0 for i in range(n+1)]for j in range(n+1)]

dp[0][0]=1.0
# for i in range(1,n+1):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

k=(n//2)+1
ans=0.0
for i in range(k,n+1):
    ans+=dp[n][i]
print(ans)
### BUGGY CODE ###

# seishin.py
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
for i in range(N, -1, -1):

    # 子ノードのqueを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # queの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[:] = a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a2*(b0 + b1 + b2) + (a0 + a1)*b2 + a1*b1) % MOD, c0+c1
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0

        Q[i] = [[1, 1, 0, 1]] + R
    else:
        Q[i] = [[1, 1, 0, 1]]
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)


### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

N, K, Q = [int(i) for i in input().split()]
A = []
for i in range(Q):
    A.append(int(input())-1)

score = [K] * N

point = [A.count(i) for i in range(N)]
minus = [Q - point[i] for i in range(len(point))]

score = [score[i] - minus[i] for i in range(len(score))]
result = ['Yes' if score[i] > 0 else 'No' for i in range(len(score))]
for i in range(len(result)):
    print(result[i])

### FIXED CODE ###

N, K, Q = [int(i) for i in input().split()]

score = [K - Q] * N

for i in range(Q):
    score[int(input())-1] += 1

for i in range(N):
    if score[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import collections, itertools, copy


class MaximumFlow:
    def ford_fulkerson(self, G, s, t):
        G = copy.deepcopy(G)

        def dfs(start, used):
            if start == t:
                return [start]
            for end, cap in G[start].items():
                if cap > 0 and end not in used:
                    used.add(end)
                    ret = dfs(end, used)
                    if ret:
                        return ret + [start]
            return []

        flow_value = 0
        flow_dict = collections.defaultdict(
            lambda: collections.defaultdict(int))
        while True:
            root = dfs(s, set([s]))
            if root:
                root = root[::-1]
                residue = min([G[a][b] for a, b in zip(root, root[1:])])
                flow_value += residue
                for a, b in zip(root, root[1:]):
                    if a in flow_dict:
                        if residue >= flow_dict[b][a]:
                            flow_dict[a][b] += residue - flow_dict[b][a]
                            del flow_dict[b][a]
                        else:
                            flow_dict[b][a] -= residue
                    else:
                        flow_dict[a][b] += residue
                    flow_dict[a][b]
                    G[a][b] -= residue
                    G[b][a] += residue
            else:
                if t in flow_dict:
                    del flow_dict[t]
                    return (flow_value, flow_dict)


N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = collections.defaultdict(lambda: collections.defaultdict(int))
for a, b in AB:
    G[-1][1000 * a + b] = 1
for c, d in CD:
    G[1000 * c + d][-2] = 1
for ab, cd in itertools.product(AB, CD):
    a, b = ab
    c, d = cd
    if a < c and b < d:
        G[1000 * a + b][1000 * c + d] = 1
flow_value, flow_dict = MaximumFlow().ford_fulkerson(G, -1, -2)
print(flow_value)


### FIXED CODE ###

N = int(input())
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            key=lambda x: x[1],
            reverse=True)
CD = sorted([[int(_) for _ in input().split()] for _ in range(N)])

for i in range(N):
    p = -1
    for j in range(len(AB)):
        if AB[j][0] < CD[i][0] and AB[j][1] < CD[i][1]:
            p = j
            break
    if p > -1:
        AB.pop(p)
print(N - len(AB))
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
SUM_P = []
for i in range(N-K+1):
    SUM_P.append(sum(p[i:i+K]))
print((max(SUM_P)+K)/2)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
SUM_P=sum(p[0:K])
all_sum_p=[SUM_P]
for i in range(N-K):
    SUM_P=SUM_P-p[i]+p[i+K]
    all_sum_p.append(SUM_P)
print((max(all_sum_p)+K)/2)
### BUGGY CODE ###

n=int(input())
s=[sorted(list(input())) for i in range(n)]
count=0

for i in range(n-1):
    for j in range(i+1,n):
        if s[i]==s[j]:
            count+=1
        
print(count)

### FIXED CODE ###

n=int(input())
s=[''.join(sorted(input())) for i in range(n)]
an={}
count=0
for i in range(n):
    if s[i] not in an:
        an[s[i]]=1
    else:
        an[s[i]]+=1
        count+=an[s[i]]-1
print(count)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

def bfs(sx, sy):
    d = [[inf for _ in range(w)] for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx, sy))

    while que:
        px, py = que.popleft()
        if a[px][py] == '#':
            return d[px][py]
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            qx, qy = px + dx, py + dy
            if 0 <= qx < h and 0 <= qy < w:
                if d[qx][qy] > d[px][py] + 1:
                    d[qx][qy] = d[px][py] + 1
                    que.append((qx, qy))

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            ans = max(ans, bfs(i, j))

print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

d = [[inf for _ in range(w)] for _ in range(h)]
que = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            d[i][j] = 0

while que:
    px, py = que.popleft()
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        qx, qy = px + dx, py + dy
        if 0 <= qx < h and 0 <= qy < w:
            if d[qx][qy] > d[px][py] + 1:
                d[qx][qy] = d[px][py] + 1
                que.append((qx, qy))

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, d[i][j])

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

import decimal,math
# from decimal import Decimal as co
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 40
import sys
sys.setrecursionlimit(1000000)
co=decimal.Decimal
n=int(raw_input())
p = map(float,raw_input().split())
dp = [[co(0)]*(n+1) for i in range(n+1)]
dp[0][0]=co(1)
for i in range(1,n+1):
	for j in range(0,i+1):
		if(j==0):
			dp[i][j]=dp[i-1][j]*(1-co(p[i-1]))
		else:
			dp[i][j]=dp[i-1][j]*(1-co(p[i-1]))+dp[i-1][j-1]*co(p[i-1])
ans=co(0.0)
for j in range(n/2+1,n+1):
	ans=ans+dp[n][j]
print ans				
			


### FIXED CODE ###

import decimal,math
# from decimal import Decimal as co
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
import sys
sys.setrecursionlimit(1000000)
# co=decimal.Decimal
n=int(raw_input())
p = map(float,raw_input().split())
dp = [[(0.0)]*(n+1) for i in range(n+1)]
dp[0][0]=(1.0)
for i in range(1,n+1):
	for j in range(0,i+1):
		if(j==0):
			dp[i][j]=dp[i-1][j]*(1-(p[i-1]))
		else:
			dp[i][j]=dp[i-1][j]*(1-(p[i-1]))+dp[i-1][j-1]*(p[i-1])
ans=(0.0)
for j in range(n/2+1,n+1):
	ans=ans+dp[n][j]
print ans