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

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    base = [i for i in range(1, 1001)]
    l = list(itertools.accumulate(base))
    r = [l[i] / (i+1) for i in range(1000)]


    maxi = 0
    ans = 0
    for i in range(N-M+1):
        s = sum(A[i:M+i])
        if maxi < s:
            ans = 0
            maxi = s
            for a in A[i:M+i]:
                ans += r[a-1]

    return ans

print(solve())

### FIXED CODE ###

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # スコアの累積和
    l = list(itertools.accumulate(A))

    score = sum(A[:M])
    for i in range(1, N-M):
        score = max(score, l[i+M] - l[i])
        
    ans = (M + score) / 2

    return ans

print(solve())
### BUGGY CODE ###

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

flag = 0
for i in range(a, b + 1):
    if i % x == 0:
        flag = flag + 1 
        break

if flag == 1:
    print((b - i) // x + flag)
else:
    print(0)

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    n = int(readline())
    *a, = map(int, readline().split())

    ctr = Counter(a)

    def prob(c1, c2, c3):
        if memo[c1][c2][c3] != -1.0:
            return memo[c1][c2][c3]

        ret = n
        if c1 > 0:
            ret += c1 * prob(c1 - 1, c2, c3)
        if c2 > 0:
            ret += c2 * prob(c1 + 1, c2 - 1, c3)
        if c3 > 0:
            ret += c3 * prob(c1, c2 + 1, c3 - 1)
        ret /= c1 + c2 + c3

        memo[c1][c2][c3] = ret
        return ret

    memo = [[[-1.0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]  # 初期値floatにして型変換をさせないようにしてみた
    memo[0][0][0] = 0.0

    ret = prob(*(ctr[k] for k in range(1, 3 + 1)))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

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

def f(L,R):
    mod_min = L*R % 2019
    for i in range(L, R):
        for j in range(i+1, R+1):
            mod = (i * j) % 2019
            if mod < mod_min:
                mod_min = mod
                if mod_min == 0:
                    break
    return mod_min
print(f(L,R))

### FIXED CODE ###

L,R = list(map(int,input().split()))
def main(L,R):
    mod_min = 2019
    if L // mod_min == R // mod_min:
        L %= mod_min
        R %= mod_min
        for i in range(L,R):
            for j in range(i+1, R+1):
                Y = i*j % 2019
                if Y < mod_min:
                    mod_min = Y
    else:
        mod_min = 0
    return mod_min
print(main(L,R))
### BUGGY CODE ###

s = list(input().rstrip())
k = int(input())
ans_list = []

for i in range(len(s)):
    for j in range(i,len(s)+1):
        a = s[i:j]
        a = "".join(a)
        ans_list.append(a)
        
ans_list = list(set(ans_list))
ans_list.sort()

print(ans_list[k])


### FIXED CODE ###

s = list(input().rstrip())
k = int(input())
ans_list = []

for i in range(len(s)):
    for j in range(i,len(s)+1):
        a = s[i:j]
        if len(a) > k:
            break
        a = "".join(a)
        ans_list.append(a)
        
ans_list = list(set(ans_list))
ans_list.sort()

print(ans_list[k])
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
A_list = sorted( list( int(i) for i in input().split() ))
BC_list = sorted(
  list( list( int(i) for i in input().split() ) for _ in range(M) ),
  key=lambda x:-x[1]
)

n = N
for bc in BC_list:
  for i in range(bc[0]):
    if bisect.bisect_right(A_list, bc[1]) < len(A_list) - N :
      pass
    bisect.insort_right(A_list, bc[1])
L = len(A_list)
print(sum(A_list[L:L-N-1:-1]))

### FIXED CODE ###

N, M = map(int, input().split())
A_list = sorted( list( int(i) for i in input().split() ))
BC_list = sorted(
  list( list( int(i) for i in input().split() ) for _ in range(M) ),
  key=lambda x:-x[1]
)

change_list = []
for bc in BC_list:
  change_list += [bc[1]] *  bc[0]
  if len(change_list) >= N :
    break
A_list += change_list
A_list.sort()
L = len(A_list)
print(sum(A_list[L:L-N-1:-1]))
### BUGGY CODE ###

N  = int(input())
nums = list(map(int,input().split()))
nums.sort()
cnt = 0
for i in range(min(nums),max(nums)+1):
  if len(list(j for j in nums if j >= i)) == N //2 :
    cnt += 1
print(cnt)

### FIXED CODE ###

N  = int(input())
nums = list(map(int,input().split()))
nums.sort()
cnt = nums[N//2] - nums[N//2-1] 
print(cnt)
### BUGGY CODE ###

K = int(input())
N = 3
def common_divisor(num1,num2):
    max_n = max(num1,num2)
    min_n = min(num1,num2)
    temp = max_n%min_n
    while True:
        if temp:
            max_n = min_n
            min_n = temp
            temp = max_n%min_n
        else:
            return min_n

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        temp = common_divisor(i,j)
        for m in range(1,K+1):
            sum = sum+common_divisor(m,temp)
print(sum)

### FIXED CODE ###

import math
K = int(input())

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        temp = math.gcd(i,j)
        for m in range(1,K+1):
            sum = sum+math.gcd(m,temp)
print(sum)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()
ans = 0
found = False
for l in range(N//2, 0, -1):
    checked = defaultdict(bool)
    for i in range(N-(2*l)+1):
        target = S[i:i+l]
        if checked[target]: continue
        if target in S[i+l:]:
            ans = l
            found = True
        else:
            checked[target] = True
        if found: break
    if found: break
print(ans)

### FIXED CODE ###

def z_algo(S):
    '''
    Input: a string S
    Output: an array Z[0..|S| - 1]
            Z[i] = l: the length of the longest prefix of S[i..|S| - 1] which is also a prefix of S,
            i.e.,
                S[j] = S[i + j] for all 0 <= j < l (l != 0),
                S[0] != S[i] (l == 0)
    Time complexity: O(|S|) time
    '''
    N = len(S)
    Z = [-1] * N
    Z[0] = N
    L = 0; R = 0 # algorithm invariant: S[L..R] is always set to be the longest common prefix of S[L..|S| - 1]
    for i in range(1, N):
        if i > R: # naive calculation
            j = 0
            while i + j < N and S[j] == S[i + j]: j += 1
            Z[i] = j
            if j > 0: L = i; R = i + j - 1
        else: # i in [L, R]
            k = i - L
            if Z[k] < R - i + 1: Z[i] = Z[k]
            else:
                L = i
                while R < N and S[R - L] == S[R]: R += 1
                Z[i] = R - L
                R -= 1
    return Z

N = int(input())
S = input()
ans = 0
for i in range(N-1):
    Z = z_algo(S[i:])
    for j, z in enumerate(Z):
        ans = max(ans, min(z, j))
print(ans)
### BUGGY CODE ###

# F
import numpy as np
from collections import deque
 
TT_list = []
# input
N, L = map(int, input().split())
T = 0.0
vt_now = 0.0
v_now = 0
que = deque()

for i in range(N):
    ti, v = map(int, input().split())
    t = float(ti)
    v_now += v
    vt_now += v*t
    # add
    if v == L:
        que.append([t, v])
    else:
        while v < L and len(que) > 0:
            t_, v_ = que.pop()
            if t_ <= t:
                que.append([t_, v_])
                que.append([t, v])
                break
            elif v + v_ >= L:
                v_ = v + v_ - L
                t = ((L - v) * t_ + v * t) / L
                v = L
                que = deque([[t, v]])
                v_now = L
                vt_now = t*L
                # break
            else:
                t = (t*v + t_*v_) / (v + v_)
                v = v + v_
    # minus
    while v_now > L:
        if que[0][1] <= v_now - L:
            v_now -= que[0][1]
            vt_now -= que[0][1]*que[0][0]
            que.popleft()
        else:
            que[0][1] -= v_now - L
            vt_now -= (v_now - L)*que[0][0]
            v_now = L
            
    TT_list.append(vt_now / L)

for i in range(N):
    print(TT_list[i])


### FIXED CODE ###

# F
from collections import deque
 
TT_list = []
# input
N, L = map(int, input().split())
T = 0.0
vt_now = 0.0
v_now = 0
que = deque()

for i in range(N):
    ti, v = map(int, input().split())
    t = float(ti)
    v_now += v
    vt_now += v*t
    # add
    if v == L:
        que.append([t, v])
    else:
        while v < L and len(que) > 0:
            t_, v_ = que[-1]
            if t_ <= t:
                que.append([t, v])
                break
            elif v + v_ >= L:
                v_ = v + v_ - L
                t = ((L - v) * t_ + v * t) / L
                v = L
                que = deque([[t, v]])
                v_now = L
                vt_now = t*L
                # break
            else:
                t = (t*v + t_*v_) / (v + v_)
                v = v + v_
                que.pop()
    # minus
    while v_now > L:
        if que[0][1] <= v_now - L:
            v_now -= que[0][1]
            vt_now -= que[0][1]*que[0][0]
            que.popleft()
        else:
            que[0][1] -= v_now - L
            vt_now -= (v_now - L)*que[0][0]
            v_now = L
            
    TT_list.append(vt_now / L)

for i in range(N):
    print(TT_list[i])
### BUGGY CODE ###

import itertools
n=int(input())
s = []
for _ in range(n):
    s.append(input())
#print(s)
#s = list(itertools.chain.from_iterable(s))
#print(s)
s_u = list(set(s))
box = []
for i in range(len(s_u)):
    box.append([s_u[i],s.count(s_u[i])])

box = sorted(box,key=lambda x:x[1],reverse=True)

ans_box = []
#ans_box.append(box[0][0])
for j in range(len(box)):
    if box[j][1] == box[0][1]:
        ans_box.append(box[j][0])
        
    else:
        break
ans_box = sorted(ans_box)
for i in range(len(ans_box)):
    print(ans_box[i])

### FIXED CODE ###

n=int(input())
dic = dict()

a = 0
for i in range(n):
    s = str(input())
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
    if dic[s] > a:
        a = dic[s]
box= []
for i in dic:
    if dic[i] == a:
        box.append(i)

ans = sorted(box)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

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

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=gcd(gcd(i,j),k)
print(ans)

### FIXED CODE ###

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

def main():
    N = int(input())
    As = list(map(int, input().split()))
    c = 0
    for i in range(N):
        l = bin(0)
        r = 0
        for ii in range(i, N):
            if (r & As[ii] != 0): break
            l = bin(int(l, 2) ^ As[ii])
            r += As[ii]
            if (l == bin(r)): c += 1

    print(c)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    x = 0
    s = 0
    r = 0
    res = 0
    for l in range(N):
        while N > r and x ^ A[r] == s + A[r]:
            x ^= A[r]
            s += A[r]
            r += 1

        x ^= A[l]
        s -= A[l]
        res += r - l

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

n = str(input())
ans,div = 0,[]
for i in range(0,len(n)):
        k = int(n[i:len(n)])
        div.append(k % 2019)
div.append(0)
for i in range(0,len(n)):
    for j in range(i+1,len(n)+1):
        if div[i] == div[j]:
            ans += 1
print(ans)

### FIXED CODE ###

import collections
n = str(input())
ans,m,div = 0,0,[]
for i,j in enumerate(reversed(n)):
    m=(m+int(j)*pow(10,i,2019))%2019
    div.append(m)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]
cnt = 0

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

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
c = Counter(s)

cnt = 0

for key in c:
    val = c[key]
    cnt += val*(val-1)//2

print(cnt)
### BUGGY CODE ###

n = int(input())

counter = 0

for i in range(1,n):
  counter += i % (i+1)
  
print(counter)

### FIXED CODE ###

n = int(input())

counter = n*(n-1)//2
  
print(int(counter))
### BUGGY CODE ###

#!/usr/bin/env python3
import numpy as np

s = str(input())

mod = 2019

div_memo = []
for i in range(1, len(s)+1):
    # print(s[len(s)-i:])
    div_memo.append(int(s[len(s)-i:]) % mod)

u, counts = np.unique(div_memo, return_counts=True)

ans = np.sum(counts*(counts-1)/2)

if u[0] == 0:
    ans += counts[0]
print(int(ans))


### FIXED CODE ###

#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(len(div_memo)):
    ans += div_memo[i]*(div_memo[i]-1)//2

ans += div_memo[0]
print(int(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
ab = [list(map(int, input().split(' '))) for i in range(n-1)]

for i in range(n-1):
    inf[ab[i][1]-1].append(ab[i][0]-1)
    inf[ab[i][0]-1].append(ab[i][1]-1)
point = [0 for _ in range(n)]
px = [list(map(int, input().split(' '))) for i in range(q)]
for i in range(q):
    point[px[i][0]-1] += px[i][1]
def add(num):
    if len(inf[num]) == 0:
        return 0
    for k in inf[num]:
        inf[k].remove(num)
        point[k] += point[num]
        add(k)
     
add(0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<nn and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)
### BUGGY CODE ###

def main():
    n,k,q = [int(x) for x in input().split()]
    a = []
    for i in range(q):
        a.append(int(input()))

    for i in range(n):
        count = a.count(i+1)
        point = k + count - q
        if point > 0:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

def main():
    n,k,q = [int(x) for x in input().split()]
    a = []
    for i in range(q):
        a.append(int(input()))

    c = collections.Counter(a)

    for i in range(n):
        index = int('{}'.format(i+1))
        point = k + c[index] - q
        if point > 0:
            print('Yes')
        else:
            print('No')


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

import sys

n = int(input())

a = []
for i in range(n):
  v = list(map(int, input().split(' ')))
  a.append(v)

f = True
day = 1
while(f):
  done = []
  nokori = 0
  for m in range(n):
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
      nokori += len(a[m])
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(S+1):
    if A[i-1] <= j:
      dp[i][j] = dp[i-1][j-A[i-1]] + (dp[i-1][j]*2)
    else:
      dp[i][j] = dp[i-1][j]*2
bad_r = sum(dp[N][math.ceil(S/2):S+1])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())
s=[]

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count(".")
    s.append(temp)

d=[[0,0]]
step=[[-1,0],[0,-1],[1,0],[0,1]]
c={(0,0):1}

while d:
    h0,w0=d.pop(0)
    s[h0][w0]="#"
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="#":
            continue
        if h==H-1 and w==W-1:
            ans = cnt - c[(h0,w0)]-1
            print(ans)
            exit()
        c[(h,w)]=c[(h0,w0)]+1
        d.append([h,w])
print(-1)

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
s=[]

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count(".")
    s.append(temp)

d=deque([[0,0]])
c=[[10000]*W for i in range(H)]
step=[[-1,0],[0,-1],[1,0],[0,1]]
c[0][0]=1

while d:
    h0,w0=d.popleft()
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="#" or c[h][w]!=10000:
            continue
        if h==H-1 and w==W-1:
            ans = cnt - c[h0][w0]-1
            print(ans)
            exit()
        c[h][w]=c[h0][w0]+1
        d.append([h,w])
print(-1)
### BUGGY CODE ###

N=int(input())


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

    # divisors.sort()
    return divisors

L=make_divisors(N)
ans=float("INF")
for n in L:
    for k in L:
        if n*k==N:
            ans=min(ans, n+k-2)
print(ans)

### FIXED CODE ###

import math
N=int(input())

A=int(math.sqrt(N))
a=1
b=1
for i in range(1, A+1):
  if N%i==0:
    a=i
    b=N/i
print(int(a+b-2))