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

n = int(input())
p = [int(i) for i in input().split()]
c = 0
for i, pi in enumerate(p):
    if pi == min(p[:i+1]):
        c += 1
print(c)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
c = 0
minp = p[0]
for pi in p:
    if pi < minp:
        minp = pi
        c += 1
print(c+1)
### BUGGY CODE ###

import math
from queue import Queue
from collections import defaultdict

n, m = [int(i) for i in input().split()]


root = defaultdict(lambda: defaultdict(int))


for i in range(m):
    a, b = [int(i) for i in input().split()]
    root[a][b] = 1
    root[b][a] = 1

check = [0 for _ in range(n + 1)]
check[1] = 1

q = Queue()
q.put(1)

while (not q.empty()):
    now = q.get()
    for i in range(1, n + 1):
        if (root[now][i] == 1 and check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n + 1):
    if (check[i] == 0):
        flag = 0

if (flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")

### FIXED CODE ###

import math
from queue import Queue

n, m = [int(i) for i in input().split()]

root = [[] for _ in range(n+1)]

for i in range(m):
    a, b = [int(i) for i in input().split()]
    root[a].append(b)
    root[b].append(a)

check = [0 for _ in range(n + 1)]
check[1] = 1

q = Queue()
q.put(1)

while (not q.empty()):
    now = q.get()
    for i in root[now]:
        if (check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n + 1):
    if (check[i] == 0):
        flag = 0

if (flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[-1]*(n+1) for _ in range(n+1)]

    def dfs(l,r):
        if(l>=r): return 0
        if(dp[l][r]!=-1): return dp[l][r]
        turn=n-(r-l)
        if(turn%2==0):
            dp[l][r]=max(dfs(l+1,r)+A[l],dfs(l,r-1)+A[r-1])
        else:
            dp[l][r]=min(dfs(l+1,r)-A[l],dfs(l,r-1)-A[r-1])
        return dp[l][r]

    print(dfs(0,n))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    dp = [[None] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][i] = 0

    for width in range(1, n + 1):
        for l in range(n):
            r = l + width
            if r > n:
                break
            turn = (n - (r - l)) & 1
            if turn & 1 == 0:
                dp[l][r] = max(A[l] + dp[l + 1][r], A[r - 1] + dp[l][r - 1])
            else:
                dp[l][r] = min(-A[l] + dp[l + 1][r], -A[r - 1] + dp[l][r - 1])


    print(dp[0][n])
resolve()
### BUGGY CODE ###

import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
already = set()
cnt = 0
ls = []
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))
### BUGGY CODE ###

import itertools
import fractions
from functools import reduce
k = int(input())
num = []
for i in range(1, k+1):
    num.append(i)
    num.append(i)
    num.append(i)
permutation_num = list(itertools.permutations(num, 3))
s = set(permutation_num)
x = []
for j in s:
    y = reduce(fractions.gcd, j)
    x.append(y)

print(sum(x))

### FIXED CODE ###

import math
k = int(input())
a = []
for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            y = math.gcd(l, x)
            a.append(y)
print(sum(a))
### BUGGY CODE ###

import itertools

def D():
    n = input()
    l = list(map(int,input().split(" ")))
    temp = list(itertools.combinations(l,3))
    count = 0
    #print(temp)
    for i in temp:
        if i[0] < i[1]+i[2] and i[1] < i[0]+i[2] and i[2] < i[0]+i[1]:
            count += 1
    print(count)

if __name__ == '__main__':
    D()
    

### FIXED CODE ###

import itertools
import bisect

def D():
    n = input()
    l = map(int,input().split(" "))
    temp = itertools.combinations(l,3)
    count = 0
    #print(temp)
    #res = [i for i in temp if i[0] < i[1]+i[2] and i[1] < i[0]+i[2] and i[2] < i[0]+i[1]]
    for i in temp:
        i = sorted(list(i),reverse=True)
        if i[0] < i[1]+i[2]:
            count += 1
    print(count)

def D_sort():
    N = int(input())
    L = sorted([int(_) for _ in input().split()])
    #L[a] + L[b] > L[c]
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect(L, L[a] + L[b] - 1) - b - 1
            #右挿入二分探索で得たインデックス-2つ目に長い辺のインデックス=その2辺で作れる三角形の個数
            #(この間に入っている辺を使う分には三角形成立条件が必ず満たされている)
    print(ans)
if __name__ == '__main__':
    D_sort()
### BUGGY CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

### FIXED CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])
### BUGGY CODE ###

import sys

s=list(input())
q=int(input())

re=False
for i in range(1,q+1):
    q_i=sys.stdin.readline().rstrip().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s=[q_i[2]]+s
        elif q_i[1]=="2" and re==True:
            s=[q_i[2]]+s
        else:
            s=s+[q_i[2]]

if re==True:
    s=s[::-1]

s="".join(s)
print(s)

### FIXED CODE ###

from collections import deque

s=list(input())
s=deque(s)
q=int(input())

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a[:n-1]:
    ans = (ans+i*(sum(a[a.index(i)+1:])))%(10**9+7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
r = sum(a)
for i in a[:n-1]:
    r = r - i
    ans = (ans+i*r)%(10**9+7)
print(ans)
### BUGGY CODE ###

def main():
    from sys import stdin
    import itertools
    n = int(stdin.readline().rstrip())
    s = str(stdin.readline().rstrip())
    g = set({})

    for key in itertools.combinations(s,3):
        g.add(key)
    
    print(len(g))
main()

### FIXED CODE ###

def main():
    from sys import stdin
    n = int(stdin.readline().rstrip())
    s = list(map(int,list(stdin.readline().rstrip())))
    ans=0
    g = set(list(range(10))) - set(s)
    for i in range(1000):
        tap = (i//100,(i//10)%10,i%10)
        if set(tap) & g == set({}):
            flag = 0
            for p in s:
                if flag == 0:
                    if p==tap[0]:
                        flag = 1
                elif flag == 1:
                    if p==tap[1]:
                        flag = 2
                elif flag == 2:
                    if p==tap[2]:
                        flag = 0
                        ans+=1
                        break
        else:
            continue

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

import os
import sys

def main():
    A , B , K = map(int , input().split())
    for i in range(0 , K) :
        if A >= 1 :
            A = A - 1
        elif A == 0 and B >= 1 :
            B = B - 1
        else :
            pass
    print (str(A) + " " + str(B))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import os
import sys

def main():
    A , B , K = map(int , input().split())
    if K >= A :
        KK = K - A
        A = 0

        if KK >= B :
            B = 0
        else :
            B = B - KK
    else :
        A = A - K
    print (str(A) + " " + str(B))

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

def primes(n: int):
    __primes = set(range(2, n + 1))
    for i in range(2, int(n ** 0.5 + 1)):
        __primes.difference_update(range(i * 2, n + 1, i))
    return list(__primes)


def main():
    n = int(input())
    pn = n
    cnt = 0
    while pn > 10 ** 7:
        pn = int(pn/10)

    prime_list = primes(pn)

    pp = []
    for p in prime_list:
        if n % p == 0:
            n /= p
            pp.append(p)
            cnt += 1
        elif n < p:
            break

    for p in pp:
        x = 2
        while True:
            q = p ** x
            if q > n:
                break

            if n % q == 0:
                n /= q
                x += 1
                cnt += 1
            else:
                break

    if pn != n and cnt == 0:
        cnt = 1
    print(cnt)


main()


### FIXED CODE ###

def is_prime(num:int):
    if num == 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    r_num = int(num ** 0.5)
    for i in range(3, r_num + 1, 2):
        if num % i == 0:
            return False
    return True


def main():
    n = int(input())

    if n == 1:
        print(0)
        return

    cnt = 0
    r_n = int(n ** 0.5)
    divided = []
    for i in range(2, n):
        if n < i:
            break
        elif cnt == 0 and r_n+1 < i:
            break
        if n % i == 0 and is_prime(i):
            n = int(n/i)
            divided.append(i)
            cnt += 1
            x = 2
            while True:
                q = i ** x
                if q > n:
                    break

                if n % q == 0:
                    n = int(n/q)
                    x += 1
                    cnt += 1
                else:
                    break
            if is_prime(n) and n not in divided:
                n = 1
                cnt += 1
                break

    if cnt == 0:
        cnt = 1
    print(cnt)


main()
### BUGGY CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0

for i in range(1,N):
    tmp = A[i:]
#    print(tmp)
    ans += A[i-1]*sum(tmp)
print(ans%mod)


### FIXED CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
v = sum(A)
for i in range(N-1):
    v -= A[i]
    ans += A[i]*v
print(ans%mod)
### BUGGY CODE ###

#-----combination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
r1,c1,r2,c2 = map(int, input().split())
#迷路の初期化


sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)

print(sum % mod)

### FIXED CODE ###

#-----combination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6*2+2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
r1,c1,r2,c2 = map(int, input().split())

def g(r,c):
    gsum = 0
    for i in range(1,r+2):
        gsum += cmb(i+c,c)
    return gsum
'''
sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)
print(sum % mod)
'''
sum2 = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(sum2 % mod)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
RGB_dict={'R':0,'G':0,'B':0}
for s in S:
  RGB_dict[s]+=1
ans=RGB_dict['R']*RGB_dict['G']*RGB_dict['B']

for i in range(N-1):
  s1=S[i]
  for j in range(i+1,N):
    s2=S[j]
    if s1==s2: continue
    k=j+(j-i)
    if k>N-1: continue
    #print(k)
    s3=S[k]
    if s1!=s3 and s2!=s3:
      ans-=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0
RGB_dict={'R':0,'G':0,'B':0}
for s in S:
  RGB_dict[s]+=1
ans=RGB_dict['R']*RGB_dict['G']*RGB_dict['B']

for i in range(N-1):
  s1=S[i]
  for j in range(i+1,N):
    s2=S[j]
    if s1==s2: continue
    k=j+(j-i)
    if k>N-1: continue
    #print(k)
    s3=S[k]
    if s1!=s3 and s2!=s3:
      ans-=1
print(ans)
### BUGGY CODE ###

N = int(input())

G = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][cur[i]]

day = 0
player = set(range(N))
while len(player) > 0:
    day += 1
    game = []
    for i in player:
        if i == edge[edge[i]]:
            game.append(i)
    if len(game) == 0:
        print(-1)
        exit()
    else:
        for j in game:
            cur[j] += 1
            c = cur[j]
            if c >= N - 1:
                player.remove(j)
            else:
                edge[j] = G[j][c]

print(day)


### FIXED CODE ###

N = int(input())

G = [list(map(int, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][0] - 1

day = 0
player = set(range(N))
cnt = 0
while len(player) > 0:
    day += 1
    game = set()
    for i in player:
        e = edge[i]
        if i == edge[e] and i != e:
            game.add(i)
            game.add(e)
    player = set()
    for j in game:
        cur[j] += 1
        c = cur[j]
        if c >= N - 1:
            edge[j] = j
        else:
            edge[j] = G[j][c] - 1
            player.add(j)

if min(cur) != N - 1:
    ans = -1
else:
    ans = day
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

for i in range(N):
    A[i + 1] += A[i]

B = [A[j] - A[i] for i in range(N) for j in range(i + 1, N + 1)]

ans = 0
t = 40
while t:
    count = 0
    tmp = pow(2, t -1)
    for b in B:
        if ((b & (tmp + ans)) == (tmp + ans)):
            count += 1
    if count >= K:
        ans += tmp
    t -= 1

print (ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

for i in range(N):
    A[i + 1] += A[i]

B = [A[j] - A[i] for i in range(N) for j in range(i + 1, N + 1)]

ans = 0
t = 40
while t:
    count = 0
    tmp = pow(2, t -1)
    for b in B:
        if ((b & (tmp + ans)) == (tmp + ans)):
            count += 1
    if count >= K:
        ans += tmp
    t -= 1

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

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    D =[int(i) for i in input().split()]
    count = 0
    D.sort()
    D.reverse()
    #print(D)
    for j in range(100000):
        if j > D[0]:
            break
        for i in range(N):
            if D[i] < j:
                if i == (N/2):
                    count+=1
                else:
                    break
    print(count)
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    D =[int(i) for i in input().split()]
    #count = 0
    D.sort()
    D.reverse()
    center = D[int(N/2)]
    print(D[int((N/2))-1]-center)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = input()
a = [int(num)  for num in input().split(" ")]

total = 0
for i in range(len(a)):
    for j in range(i+1, len(a)):
        total += (a[i]*a[j]) % (10**9 + 7)
print(total% (10**9 + 7))


### FIXED CODE ###

n = input()
a = [int(num) for num in input().split(" ")]

mod_value = 10**9 + 7

sum = 0
total = 0
for i in reversed(range(1, len(a))):
    sum += a[i]
    total += a[i-1] * sum

print(total%mod_value)
### BUGGY CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        for x, val in enumerate(list(input().rstrip())):
            if val == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q[:]
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

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

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

B=[]
C=[]
ans_list=[]
ans=0

for i in range(M):
  b,c=map(int, input().split() )
  B.append(b)
  C.append(c)

while B:
  max_index=C.index(max(C))
  max_value=B[max_index]

  for i in range(max_value):
    ans_list.append(max(C))

  B.pop(max_index)
  C.pop(max_index)

new_list=A+ans_list
new_list.sort(reverse=True)

for i in range(N):
  ans+=new_list[i]

print(ans)	

### FIXED CODE ###

from collections import Counter

N,M = map(int, input().split() )
A   = list(map(int, input().split() ))
B   = [0]*M
C   = [0]*M
Cou = Counter(A)

for i in range(M):
  B[i],C[i]  = map(int, input().split() )
  Cou[C[i]] += B[i]
  
#print(Cou)  
ans=0
cnt=0
S=sorted(Cou,reverse=True)
#print(S)
for num in S:
  kosuu = min(Cou[num],N-cnt)
  cnt += kosuu
  ans += num*kosuu
  
print(ans)
### BUGGY CODE ###

from collections import deque
M = int(input())
deq = deque()

for _ in range(M):
  d,c = map(int,input().split())
  for _ in range(c):
    deq.append(d)

def is_handred():
  if deq[0]==1 and deq[1]==0 and deq[2]==0:
    return True
  return False

times = 0
while len(deq) > 1:
  if len(deq) == 3 and is_handred():
    deq = deque([1,0])
  else:
    i,j = deq.popleft(), deq.popleft()
    for x in list(str(i+j)):
      deq.append(int(x))

  times += 1

print(times)

### FIXED CODE ###

M = int(input())

cur = 0

keta = 0
csum = 0
for _ in range(M):
  d,c = map(int,input().split())
  s = 0
  for i in str(d):
    s += int(i)
  csum += s * c
  keta += c

# 9をカウントしたくないため
print(keta-1 + (csum-1)//9)
### BUGGY CODE ###

N = int(input())
a = [set() for _ in range(N)]

for i in range(N):
    id = int(input()) - 1
    a[id].add(i)

step = -1
already = a[1]
now = a[1]
next = set()
for i in range(N-1):
    already = already.union(now)
    if 0 in now:
        step = i+1
        break
    for j in now:
        next = next.union(a[j])
    now = next
    next = set()

print(step)

### FIXED CODE ###

N = int(input())
a = [set() for _ in range(N)]

for i in range(N):
    id = int(input()) - 1
    a[id].add(i)

step = -1
#already = a[1]
now = a[1]
next = set()
for i in range(N-1):
    #already = already.union(now)
    if 0 in now:
        step = i+1
        break
    for j in now:
        next = next.union(a[j])
    now = next
    next = set()

print(step)
### BUGGY CODE ###

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

dp = [0] * N
for i in range(1, N):
    # 現在の足場を1~K前の足場から求める
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0,i-K),i)])

print(dp[-1])


### FIXED CODE ###

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

dp = [0] * N
for i in range(1, N):
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0,i-K),i)])

print(dp[-1])
### BUGGY CODE ###


def get_expected_value(n):

    expected_value = 0
    for i in range(1,n+1):
        expected_value += i / n
    return expected_value

def main():
    n, k = map(int,input().split())
    pn = list(map(int,input().split()))
    expected_value_sum_max = 0
    for i in range(n-k+1):
        tmp = 0
        for j in range(k):
            tmp += get_expected_value(pn[i+j])

        if tmp > expected_value_sum_max:
            expected_value_sum_max = tmp

    print(expected_value_sum_max)

if __name__ == '__main__':
  	main()

'''
5 3
1 2 2 4 5
'''

### FIXED CODE ###

from itertools import accumulate

def main():
    N, K= map(int, input().split())
    p = list(map(int, input().split()))
    # 累積和
    p = [0] + list(accumulate(p))

    # 累積和が最大になる区間、期待値は(1+p)/2、k個分なので以下の式。
    print((max(b - a for a, b in zip(p, p[K:])) + K) / 2)

if __name__ == '__main__':
  	main()

'''
5 3
1 2 2 4 5

10 4
17 13 13 12 15 20 10 13 17 11
'''