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

H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, # current x
        0, # current y
        0, # count
    ))

    while q:
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '#':
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
            

shortest_path_len = bfs()

cnt_dot = sum([s.count('.') for s in maze])


#print(shortest_path_len)
#print(cnt_dot)

ans = cnt_dot - shortest_path_len - 1
print(ans)
#print(stayed)
        
        
        

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, # current x
        0, # current y
        0, # count
    ))

    while not q.empty():
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '#':
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
                
        #print(stayed)
    return -1
            

shortest_path_len = bfs()

if shortest_path_len != -1:
    cnt_dot = sum([s.count('.') for s in maze])


    ans = cnt_dot - shortest_path_len - 1
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N,K = map(int,input().split())
list1 = []
for i in range(N):
    a,b = map(int,input().split()) 
    list2 = [a]*b
    list1 += list2
list1.sort()
print(list1[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
list1 = []
for i in range(N):
    list1.append(list(map(int,input().split())))
num = [0]*(10**5+1)
for j in range(N):
    num[list1[j][0]] += list1[j][1]
c = 0
d = 0
for k in range(10**5+1):
    c += num[k]
    if c >= K:
        d = k
        break
print(d)
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
num = 0

for i in range(N):
  Sorted = sorted(List[:i+1])
  if Sorted[0] == List[i]:
    num += 1
print(num)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
num = 0
min = List[0]
for i in range(N):
  if List[i] <= min:
    num += 1
    min = List[i]
print(num)
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    S = list(input())
    ls = len(S)
    l = [1] * ls
    nl = [0] * ls
    for _ in range(ls*2):
        for i in range(ls):
            if S[i] == 'R':
                nl[i + 1] += l[i]
            else:
                nl[i - 1] += l[i]
        for j in range(ls):
            l[j] = nl[j]
            nl[j] = 0
    print(*l)


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

num_city, num_train, num_question = [int(i) for i in input().split()]

trains = []
for i in range(0, num_train):
    trains.append([int(j) for j in input().split()])

answers = []
for i in range(0, num_question):
    question = [int(j) for j in input().split()]

    count = 0
    for train in trains:
        if question[0] <= train[0] and question[1] >= train[1]:
            count += 1
    answers.append(count)

for answer in answers:
    print(answer)


### FIXED CODE ###

num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
cumlative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] = cumlative_sum[start][arrive - 1] + trains[start][arrive]

for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] += cumlative_sum[start - 1][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = cumlative_sum[arrive][arrive] - cumlative_sum[start - 1][arrive] - cumlative_sum[arrive][start - 1] + cumlative_sum[start - 1][start - 1]
    print(result)
### BUGGY CODE ###

N, K = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
sum_max = 0
sum_max_index = 0
for i in range(N-K+2):
  #print(i)
  tmp_sum = sum(p[i:i+K])
  #print(sum_max)
  if sum_max < tmp_sum:
    sum_max = tmp_sum
    sum_max_index = i
total_num = 0
for i in range(sum_max_index,sum_max_index+K):
  total_num += (p[i]+1)/2
print(total_num)

### FIXED CODE ###

N, K = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
p_ex = [(i+1)/2 for i in p]
sum_list = [sum(p_ex[0:K]),sum(p_ex[N-K:N])]
tmp_num = sum_list[0]
if N == K:
  print(sum(p_ex))
else:
  for i in range(1,N-K):
    #print("i:"+str(i))
    tmp_num = tmp_num - p_ex[i-1] + p_ex[i+K-1]
    #print("  tmp_num = tmp_num - "+str(p_ex[i-1])+" + "+str(p_ex[i+K-1]))
    sum_list.append(tmp_num)
  print(max(sum_list))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0
for i in range(61):
    a,b=0,0
    for j in range(N):
        if A[j]%2==0:
            a+=1
        else:
            b+=1
        A[j]=A[j]//2
    ans=(ans+(a*b)*2**i)%MOD
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0
for i in range(60):
    a,b=0,0
    for j in range(N):
        if A[j]%2==0:
            a=a+1
        else:
            b=b+1
        A[j]=A[j]//2
    ans=(ans+(a*b)*2**i)%MOD
print(ans)
### BUGGY CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

ans = 0
for i in range(N):
    flg = 0
    j = 0
    while j < i:
        if S[j] == S[i]:
            flg = 1
            break
        j += 1
    if flg == 0:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())

ans = set()

for i in range(N):
    S = input()
    if S in ans:
        continue
    else:
        ans.add(S)

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

S = input()

#S_mod = [0] * (len(S)+1)

mod_count = [0] * 2019
mod_count[0] = 1

for i in range(len(S)):
    mod_count[int(S[i:len(S)])%2019] += 1
    
#print(S_mod)

#for i in range(len(S_mod)):
#    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))



### FIXED CODE ###

S = input()[::-1]

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

mod_count = [0] * 2019

d = 10

#for i in range(len(S)):
#    S_mod[i] = int(S[i:len(S)])%2019

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))
### BUGGY CODE ###


def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':(-1,-1),'1':(1,1),'?':(-1,1)}
    S = [d[c] for c in S]

    def judge(target_lo, target_hi):
        lo = 0
        hi = 0

        pl = target_lo%2 == 0
        ph = target_hi%2 == 0

        for a,b in S:
            lo = max(lo+a, target_lo+pl)
            hi = min(hi+b, target_hi-ph)
            if hi < lo:
                return False
            pl = not pl
            ph = not ph
        return True

    best = 10**6*2
    lo = -10**6
    hi = 10**6
    while True:
        hi = bisect(-1,10**6, lambda x: judge(lo, x))
        lo = bisect(1, -10**6, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, -10**6, lambda x: judge(x, hi))
    return min(best, hi-lo)

from itertools import product, accumulate
from random import shuffle

def naive(S):
    d = {'0':(-1,), '1':(1,), '?': (-1,1)}
    return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))

### FIXED CODE ###


def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':0,'1':1,'?':2}
    S = tuple(d[c] for c in S)
    lookup = ((-1,-1),(1,1), (-1,1))

    def judge(target_lo, target_hi):
        lo,hi = 0,0
        pl = target_lo%2 == 0
        ph = target_hi%2 == 0
        for s in S:
            a,b = lookup[s]
            lo = max(lo+a, target_lo+pl)
            hi = min(hi+b, target_hi-ph)
            if hi < lo:
                return False
            pl = not pl
            ph = not ph
        return True

    best = 10**6*2
    n0,n1,n2 = S.count(0), S.count(1), S.count(2)
    lo = -n0-n2
    hi = n1+n2
    while True:
        hi = bisect(-1, hi, lambda x: judge(lo, x))
        lo = bisect(1, lo, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, lo, lambda x: judge(x, hi))
    return min(best, hi-lo)

# from itertools import product, accumulate
# from random import shuffle

# def naive(S):
#     d = {'0':(-1,), '1':(1,), '?': (-1,1)}
#     return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))
### BUGGY CODE ###

from bisect import bisect_right

while True:
    n, m = map(int, input().split())
    if not n:
        break

    ps = [0] + sorted(int(input()) for _ in range(n))

    p2 = set()
    for i, pi in enumerate(ps):
        for pj in ps[i:]:
            if pi + pj > m:
                break
            p2.add(pi + pj)

    p2 = sorted(p2)

    max_s = 0
    for pi in p2:
        j = bisect_right(p2, m - pi)
        s = pi + p2[j - 1]
        if max_s < s:
            max_s = s
    print(max_s)

### FIXED CODE ###

from bisect import bisect_right

while True:
    n, m = map(int, input().split())
    if not n:
        break

    ps = [0] + sorted(int(input()) for _ in range(n))

    p2 = set()
    for i, pi in enumerate(ps):
        for pj in ps[i:]:
            if pi + pj > m:
                break
            p2.add(pi + pj)

    p2 = sorted(p2)

    print(max(pi + p2[bisect_right(p2, m - pi) - 1] for pi in p2))
### BUGGY CODE ###

from collections import defaultdict
from itertools import accumulate

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

acc=list(accumulate(A))

d=[defaultdict(int) for i in range(N+1)]

for i in range(N):
    d[i+1][acc[i]%M]+=1
    for n,m in d[i].items():
        d[i+1][n]+=m

ans=0
for g in range(N):
    if acc[g]%M==0:
        ans+=d[g+1][acc[g]%M]
    else:
        ans+=d[g+1][acc[g]%M]-1
print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate

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

acc=list(accumulate(A))

d=defaultdict(int)

ans=0
for i in range(N):
    if acc[i]%M==0:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]
    else:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]-1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
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()

from collections import Counter

def main():
    N = II()
    A = LI()
    def func(arr):
        if len(arr) == 0:
            return 0
        a = min(arr)
        idx = arr.index(a)
        return (idx + 1) * (len(arr) - idx) * a + func(arr[:idx]) + func(arr[idx + 1:])
    ans = func(A)

    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
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()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
res = a[0]
a.pop(0)
cnt = n - 2
while cnt > 0:
    if cnt >= 2:
        res += a.pop(0) * 2
        cnt -= 2
    
    elif cnt == 1:
        res += a.pop(0)
        cnt -= 1
    
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
res = a[0]
a.pop(0)

num = (n - 2) // 2
num1 = (n - 2) % 2
res += sum(a[:num]) * 2 + a[num] * num1
print(res)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
case = []
for i in range(M):
  case.append(list(map(int, input().split())))

B = A[:]
C = []
for i in range(M):
  for j in range(case[i][0]):
    C.append(case[i][1])

while min(B) < max(C):
  B.append(max(C))
  B.remove(min(B))
  C.remove(max(C))
  if len(B) == 0 or len(C) == 0:
    break
  
S = 0
for i in range(len(B)):
  S += B[i]

print(S)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = []
for i in range(M):
  B, C = map(int, input().split())
  D.append([C, B])
D.sort(reverse=True)
E = []
j = 0
for i in range(N):
  if j < M:
    if D[j][1] == 0:
      j += 1
    if j == M:
      E.append(0)
    else:
      E.append(D[j][0])
      D[j][1] -= 1
  else:
    E.append(0)
S = 0
for i in range(N):
  S += max(A[i], E[i])
print(S)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    dots = []
    for _ in range(N):
        x, y = map(int, input().split())
        dots.append((x,y))

    ans = float('inf')

    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if i == j == k == l:
                        continue
                    right = max(dots[i][0],dots[j][0],dots[k][0],dots[l][0])
                    left = min(dots[i][0],dots[j][0],dots[k][0],dots[l][0])
                    bottom = min(dots[i][1],dots[j][1],dots[k][1],dots[l][1])
                    top = max(dots[i][1],dots[j][1],dots[k][1],dots[l][1])

                    cnt = 0
                    for x, y in dots:
                        if left <= x <= right and bottom <= y <= top:
                            cnt += 1

                    if cnt >= K:
                        ans = min(ans, (top - bottom) * (right - left))
    print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = map(int, input().split())

    ans = float('inf')
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        cnt = 0
                        lx = x[i]
                        rx = x[j]
                        by = y[k]
                        uy = y[l]

                        for n in range(N):
                            if lx <= x[n] and x[n] <= rx and by <= y[n] and y[n] <= uy:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (rx - lx) * (uy - by))

    print(ans)

main()
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    s = str(i)
    num = [0]*3
    if len(s) == 1:
        num[2] = i
    elif len(s) == 2:
        num[1] = int(s[0])
        num[2] = int(s[1])
    else:
        num[0] = int(s[0])
        num[1] = int(s[1])
        num[2] = int(s[2])
    flag2 = True
    start = 0
    for j in range(3):
        flag = False
        for k in range(start,N):
            if num[j] == int(S[k]):
                flag = True
                start = k+1
                break
        if flag == False:
            flag2 = False
            break    
    if flag2:
        ans+=1
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    flag2 = True
    start = 0
    for j in range(3):
        flag = False
        for k in range(start,N):
            if num[j] == S[k]:
                flag = True
                start = k+1
                break
        if flag == False:
            flag2 = False
            break    
    if flag2:
        ans+=1
    
print(ans)
### BUGGY CODE ###

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

dp = [float('inf')] * (2 ** N)


dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum(1 << (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        dp[c | x] = min(dp[c | x], dp[x] + a)

if dp[-1]==float('inf'):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf')] * (2 ** N)


dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum(1 << (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        dp[c | x] = min(dp[c | x], dp[x] + a)

if dp[-1]==float('inf'):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

s=input()
def roopR(l,n):
  if list[k]==1:
    for p in range(a):
      if list[l]==-1 and n%2==0:
        return l
      elif list[l]==-1 and n%2==1:
        return l-1
      else:
        l += 1
        n += 1
  else:
    for q in range(a):
      if list[l]==1 and n%2==0:
        return l
      elif list[l]==1 and n%2==1:
        return l+1
      else:
        l -= 1
        n += 1

a=len(s)
endlist=[]
list=[]
for i in range(a):
  if s[i]=='R':
    list.append(1)
  else:
    list.append(-1)
for j in range(a):
  endlist.append(0)
for k in range(a):
  b=roopR(k,0)
  endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
### BUGGY CODE ###

from random import randint
mod=(1<<150)-1#1370757747362922367
rr=randint(2,mod-2)
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&mod
    #h=(h+b*r)%mod
    #r=r*rr%mod
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
m=2**150-1
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&m
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)
### BUGGY CODE ###

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

for i in range(N):
  if i+1+A[i]< N:
    for j in range(i+1+A[i],N):
      if j-i == A[i] +A[j]:
        count += 1
print(count)
    
        

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = [ A[i] - (i+1) for i in range(N)]
c = Counter(a)
count = 0
for i in range(N-1):
  count += c[-1*(A[i] + (i+1))]
  c[A[i]-(i+1)] -= 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
K = int(input())

# lcm & gcd not math library
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
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(gcd(i, j), k)

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K = int(input())

# lcm & gcd not math library
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

from functools import reduce
def gcd_multi(num_list):
    return reduce(gcd, num_list)

ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j and j == k:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += gcd_multi([i, j, k]) * dup_num

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

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(n+1) for i in range(n+1)]

import sys
x=5000
sys.setrecursionlimit(x)
def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

### FIXED CODE ###


n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(n+1) for i in range(n+1)]
def func(n,x):
    for i in range(0,n+1):
        for j in range(0,n+1):
            if j==0:
                dp[i][j] = 1
            elif i==0:
                dp[i][j]=0
            else:
                p=(arr[i-1])*dp[i-1][j-1]
                q=(1-arr[i-1])*dp[i-1][j]
                dp[i][j] = p+q 
    
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))