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

class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[BinaryIndexedTree(2*n)for _ in range(n+1)]
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  dp[i][0]=0
  for k in range(i):
    dp[i][0]+=w[k]+bit[i].sum(w[k],2*n-1)-k
    bit[i].add(w[k],1)
for j in range(n):
  for i in range(n+1):
    if i==0:
      dp[i][j+1]=dp[i][j]+b[j]+bit[i].sum(b[j],2*n-1)-(i+j)
    else:
      dp[i][j+1]=dp[i][j]+(b[j]+bit[i].sum(b[j],2*n-1)-(i+j))
      dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+bit[i-1].sum(w[i-1],2*n-1)-(i+j)))
    bit[i].add(b[j],1)
print(dp[n][n])

### FIXED CODE ###

n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[0]*2*n
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  bitt=bit[:]
  for j in range(n):
    a=0
    k=2*n
    while k:
      a+=bitt[k-1]
      k-=k&-k
    if w[j]!=0:
      k=w[j]
      while k:
        a-=bitt[k-1]
        k-=k&-k
    dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a+w[j]-(i+j))
    k=w[j]+1
    while k<=2*n:
      bitt[k-1]+=1
      k+=k&-k
    if i!=n:
      a=0
      k=2*n
      while k:
        a+=bitt[k-1]
        k-=k&-k
      if b[i]!=0:
        k=b[i]
        while k:
          a-=bitt[k-1]
          k-=k&-k
      dp[i+1][j+1]=dp[i][j+1]+a+b[i]-(i+j+1)
  if i!=n:
    a=b[i]-i
    k=2*n
    while k:
      a+=bit[k-1]
      k-=k&-k
    if b[i]!=0:
      k=b[i]
      while k:
        a-=bit[k-1]
        k-=k&-k
    dp[i+1][0]=dp[i][0]+a
    k=b[i]+1
    while k<=2*n:
      bit[k-1]+=1
      k+=k&-k
print(dp[n][n])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
memo = {}

tmp = 1
for i in range(k):
    tmp *= a[i]
memo[k-1] = tmp

for i in range(k,n):
    before = memo[i-1]
    after = 1
    for j in range(k):
        after *= a[i-j]
    
    if before < after:
        print("Yes")
    else:
        print("No")
    
    memo[i] = after



### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
memo = {}

for i in range(k,n):
    if a[i] > a[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(k):
    for b in range(k):
        for c in range(k):
            GCDab = math.gcd(a+1, b+1)
            GCDabc = math.gcd(GCDab, c+1)
            ans += GCDabc
print(ans)

### FIXED CODE ###

import math
k = int(input())
ansA, ansB, ansC = 0, 0, 0
for a in range(k):
    ansC += a+1
    for b in range(k-a-1):
        GCDab = math.gcd(a+1, a+b+2)
        ansB += GCDab
        for c in range(k-a-b-2):
            GCDabc = math.gcd(GCDab, a+b+c+3)
            ansA += GCDabc
ans = ansA * 6 + ansB * 6 + ansC
print(ans)
### BUGGY CODE ###


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


from sys import stdin
import math

L,R  = [int(x) for x in stdin.readline().rstrip().split()]

diff = R - L

min_val = 2019

for i in range(L,R+1):
    for j in range(i+1,R+1):
        amari = (i * j) % 2019
        if ( min_val > amari ):
            min_val = amari

print(min_val)


### FIXED CODE ###

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


from sys import stdin
import math

L,R  = [int(x) for x in stdin.readline().rstrip().split()]

diff = R - L

min_val = 2019



min_val = 2019

sur_L = L % 2019
sur_R = R % 2019

if diff > 2019:
    print(0)

elif sur_R < sur_L:
    print(0)
else:
    if sur_R < sur_L:
        tmp = sur_R
        sur_R = sur_L
        sur_L = tmp
        

    for i in range(sur_L,sur_R+1):
        for j in range(i+1, sur_R+1):
            amari = ( i * j) % 2019
            if min_val > amari:
                min_val = amari

    print(min_val)
### BUGGY CODE ###

import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1


def factorList(n):
    # [素因数]=数を出力
    f = {}
    c = 0
    r = int(n**0.5)
    l = []
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            l.append([i, c])
            c = 0
    if n != 1:
        l.append([n, 1])
    return l


def cmb(a, i, h, t):
    if i >= len(a):
        return h[t]
    for j in range(a[i][1]+1):
        d = cmb(a, i+1, h, t*pow(a[i][0], j))
        if d:
            return True
    return False


h = [False]*(10**6+1)
ans = 0
for n, c in a:
    if c == 1:
        fl = factorList(n)
        if not cmb(fl, 0, h, 1):
            ans += 1
    h[n] = True

print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [0]*(10**6+1)
for i in range(N):
    if d[A[i]] == 0:
        if c[A[i]] == 1:
            ans += 1
        j = A[i]
        while j <= (10**6):
            d[j] += 1
            j += A[i]
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
dp = np.zeros((n + 1, 3), dtype=int)
for i in range(n):
    abc = list(map(int, input().split()))
    for j in range(3):
        for k in range(1, 3):
            k = (j + k) % 3
            dp[i + 1, j] = max(dp[i + 1, j], dp[i, k] + abc[k])
print(dp[-1].max())

### FIXED CODE ###

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

# i日目にjを選択した後の幸福度 dp[i][j]
dp = [[0 for j in range(3)] for i in range(n + 1)]

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + ABC[i][k])

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

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

if K == 1:
    print(0)
    exit()
else:
    for i in range(100000000):
        k = abs(N-K)
        if k < N:
            N = k                
print(N)

### FIXED CODE ###

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

if K == 1:
    print(0)
    exit()
elif N == 0:
    print(0)
    exit()    
else:
    a = N-K*(N//K)
    b =abs(N-K*(N//K +1))
    print(min(a,b))
### BUGGY CODE ###

from collections import namedtuple

Item = namedtuple('Item', 'w v')

N, W = (int(x) for x in input().split())

items = []

for _ in range(N):
  w, v = (int(x) for x in input().split())
  items.append(Item(w, v))

memo = [[0] * (W + 1) for _ in range(N)]

for i in range(N):
  for w in range(W + 1):
    if i == 0:
      # 1行目を初期化
      memo[i][w] = items[i].v if items[i].w <= w else 0
      continue
    if w < items[i].w:
      # 入らなければひとつ上の行の値をそのまま使う
      memo[i][w] = memo[i - 1][w]
      continue
    memo[i][w] = max(memo[i - 1][w], memo[i - 1][w - items[i].w] + items[i].v)

print(memo[N - 1][W])

### FIXED CODE ###

from collections import namedtuple


Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))

memo = [0] * (W + 1)

for item in items:
  for w in range(W, item.w - 1, -1):
    memo[w] = max(memo[w], memo[w - item.w] + item.v)
    
print(memo[W])
### BUGGY CODE ###

n = int(input())
p = [None]*(n+1)
p[0] = 1

for i in range(1,n+1):
    p[i] = p[i-1]*i

print(p[i]%1000000007)


### FIXED CODE ###

n = int(input())
p = 1
for i in range(1, n + 1):
    p = p * i % 1000000007

print(p)
### BUGGY CODE ###

import heapq as h

N,M=map(int,input().split())
hen=[[] for i in range(0,N)]
for i in range(0,M):
    u,v=map(int,input().split())
    hen[u-1].append(v-1)

S,T=map(int,input().split())

ans=[-1 for i in range(0,N)]
ans[S-1]=0

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
flag=1
while flag==1:
    flag=0
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
                h.heappush(sub,p)
        if q==[]:
            count+=1
            if count%3==0:
                for j in sub:
                    if ans[j]==-1:
                        ans[j]=count//3
                        flag=1
            else:
                flag=1
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

### FIXED CODE ###

import heapq as h

N,M=map(int,input().split())
hen={(i,j):[] for i in range(0,N) for j in range(0,3)}
for i in range(0,M):
    u,v=map(int,input().split())
    hen[(u-1,0)].append((v-1,1))
    hen[(u-1,1)].append((v-1,2))
    hen[(u-1,2)].append((v-1,0))

S,T=map(int,input().split())

start=(S-1,0)
goal=(T-1,0)

distance={(i,j):-1 for i in range(0,N) for j in range(0,3)}

q=[]
q.append(start)
distance[start]=0
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if distance[p]==-1:
                h.heappush(sub,p)
                distance[p]=distance[x]+1
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

if distance[goal]==-1:
    print(-1)
else:
    print(distance[goal]//3)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * n
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))

print(dp[-1])


### FIXED CODE ###

import sys
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,sys.stdin.readline().split())))

dp = np.zeros(n, dtype=int)
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    #dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))
    dp[i] = (dp[x:i] + abs(h[i] - h[x:i])).min()
print(dp[-1])
### BUGGY CODE ###

n = int(input())

L = []
ans = 0
for i in range(n):
    tmp = int(input())
    if tmp in set(L):
        L = [i for i in L if i != tmp]
    else:
        L.append(tmp)

print(len(L)) 

### FIXED CODE ###

n = int(input())

L = set([])

for i in range(n):
    tmp = int(input())
    if tmp in L:
        L.remove(tmp)
    else:
        L.add(tmp)

print(len(L))
### BUGGY CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

for i in second:
	if i in first:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

first=set(first)
second=set(second)
if len(first.intersection(second))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y)%(prime), an ,0 )

print(ans)

### FIXED CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

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

import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = np.argmin(np.abs(a - t))
    b_dis = np.argmin(np.abs(b - t))
    a_d = np.abs(a[a_dis] - t)
    b_d = np.abs(b[b_dis] - t)
    cand1 = b_d + np.min(np.abs(a[np.max([a_dis-1,0]):a_dis+1] - b[b_dis]))
    cand2 = a_d + np.min(np.abs(b[np.max([b_dis-1,0]):b_dis+1] - a[a_dis]))
    print(np.min([cand1, cand2]))

### FIXED CODE ###

import bisect
import numpy as np
 
hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

def search_min_pos(arr, target):
  index = bisect.bisect_left(arr, target)
  if 0 == index:
    dist = arr[index]
  else:
    dist = arr[index-1:index+1]
  if not isinstance(dist, list):
    dist = [dist]
  return dist

a_arr = s[:hint[0]]
b_arr = s[hint[0]:-hint[2]]
sum = 0
for t in s[-hint[2]:]:
  a_pos = search_min_pos(a_arr, t)
  b_pos = search_min_pos(b_arr, t)
  #print(t, a_pos, b_pos)
  min_dist = 10 ** 11
  for a in a_pos:
    b_against_a = search_min_pos(b_arr, a)
    for ba in b_against_a:
      min_dist = min([min_dist, abs(t-a)+abs(ba-a)])
  for b in b_pos:
    a_against_b = search_min_pos(a_arr, b)
    for ab in a_against_b:
      min_dist = min([min_dist, abs(t-b)+abs(ab-b)])
  print(min_dist)
### BUGGY CODE ###

mod=10**9+7
n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
a=[int(input()) for _ in range(m)]

if 0 in a:
    print(0)
    exit()
for i in range(n):
    if i+1 not    in a:
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    if i+2<=n and i+2 not  in a:
        dp[i+2]+=dp[i]
        dp[i+1]%=mod
print(dp[-1]%mod)

### FIXED CODE ###

N,M = map(int,input().split())
A = set([int(input()) for i in range(M)])
MOD = 10**9+7

if 0 in A:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1])
### BUGGY CODE ###

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

cnt = 1

for i in reversed(range(1, N)):
    if P[i] < min(P[:i]):
        cnt += 1

print(cnt)


### FIXED CODE ###

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

cnt = 1
p_min = P[0]

for i in range(1, N):
    if P[i] < p_min:
        cnt += 1
        p_min = P[i]

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

#Thanks, snuke!

N,M = map(int,input().split())
key = []
for i in range(M) :
    a,b = map(int,input().split())
    s = 0
    cx = list(map(int,input().split()))
    for j in range(b) :
        s = s | (1 << (cx[j]-1))
    key.append([s,a])

dp = [10**12 for i in range(1 << N)]
dp[0] = 0
for s in range(1 << N) :
    for i in range(M) :
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)

ans = dp[-1] if dp[-1] != 10**12 else -1

print(ans)


### FIXED CODE ###

#Thanks, snuke!

N,M = map(int,input().split())
key = []
for i in range(M) :
    a,b = map(int,input().split())
    s = 0
    cx = list(map(int,input().split()))
    for j in range(b) :
        s = s | (1 << (cx[j]-1))
    key.append([s,a])

dp = [10**12 for i in range(1 << N)]
dp[0] = 0
for s in range(1 << N) :
    for i in range(M) :
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)

ans = dp[-1] if dp[-1] != 10**12 else -1

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

import sys
sys.setrecursionlimit(6009)
s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	if min(x,y)<=-1:
		return ""
	if s[x]==t[y]:
		return lcs(x-1,y-1)+s[x]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		return a
	else:
		return b
print(lcs(n-1,m-1))

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
### BUGGY CODE ###

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

while M > 0:
    maxv = max(A)
    max_index = A.index(maxv)
    A[max_index] = A[max_index] // 2
    M -= 1

print(sum(A))


### FIXED CODE ###

import heapq


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

A = [a * -1 for a in A]

heapq.heapify(A)
for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, (-a // 2) * (-1))

print(-sum(A))
### BUGGY CODE ###

s=input()
t=input()

l1,l2 = len(s),len(t)

dp = [[0]*(l2+1) for _ in range(l1+1)]
memo = [['']*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      memo[i][j] = s[i-1]
    else:
      if dp[i-1][j] >= dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        memo[i][j] = (i-1,j)
      else:
        dp[i][j] = dp[i][j-1]
        memo[i][j] = (i,j-1)
      
i,j = l1,l2
ans = ''
while i > 0 and j > 0:
  if len(memo[i][j]) == 2:
    i, j = memo[i][j]
  else:
    ans = memo[i][j] + ans
    i, j = i-1, j-1
    
print(ans)

### FIXED CODE ###

s=input()
t=input()

l1,l2 = len(s),len(t)

dp = [[0]*(l2+1) for _ in range(l1+1)]
memo = [['']*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      memo[i][j] = s[i-1]
    else:
      if dp[i-1][j] >= dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        memo[i][j] = (i-1,j)
      else:
        dp[i][j] = dp[i][j-1]
        memo[i][j] = (i,j-1)
      
i,j = l1,l2
ans = []
while i > 0 and j > 0:
  if len(memo[i][j]) == 2:
    i, j = memo[i][j]
  else:
    ans.append(memo[i][j])
    i, j = i-1, j-1
    
print(''.join(ans[::-1]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    b = 0
    bud = 0
    for j, ai in enumerate(a):
        if i != j:
            bud += abs(ai - b)
            b = ai
    bud += abs(b)
    print(bud)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.append(0)
a.insert(0, 0)
costs = []
for i in range(n + 1):
    costs.append(abs(a[i + 1] - a[i]))

s = sum(costs)
for i in range(n):
    print(s - costs[i] - costs[i + 1] + abs(a[i] - a[i + 2]))
### BUGGY CODE ###

def main():
    s = input()
    a = "".join(["".join(["1"for j in range(i-3) if int(s[j:i])%2019==0]) for i in range(len(s)+1)])
    print(len(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

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

n, k = map(int, input().split())
p = tuple(map(int, input().split()))

prev = 0
ind = 0
for i in range(n - k + 1):
    nex = 0
    for j in range(i, i + k):
        nex += p[j]

    if prev < nex:
        prev = nex
        ind = i

total = 0
for i in range(ind, ind + k):
    total += (1 + p[i]) * (p[i] / 2) / p[i]

print(total)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

prev = sum(p[1:k])
current = sum(p[1:k])
ind = 0

for i in range(1, n - k + 1):
    current = current - p[i - 1] + p[i + k - 1]

    if prev < current:
        prev = current
        ind = i

total = 0
for i in range(ind, ind + k):
    total += p[i] / 2 + 0.5

print(total)
### BUGGY CODE ###

import heapq
INFTY = 10**10
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,z = map(int,input().split())
    if x not in G:
        G[x]=[]
    G[x].append(y)
    if y not in G:
        G[y]=[]
    G[y].append(x)
cnt = N-len(G)
while G:
    K = len(G)
    d = {i:INFTY for i in G.keys()}
    k = list(G.keys())[0]
    d[k]=0
    hist = {i:0 for i in G.keys()}
    heap = [(0,k)]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in G[cur[1]]:
            if hist[x]==0:
                if d[cur[1]]+1<d[x]:
                    d[x] = d[cur[1]]+1
                    heapq.heappush(heap,(d[x],x))
    A = list(G.keys())
    for i in A:
        if hist[i]==1:
            del G[i]
    cnt += 1
print(cnt)

### FIXED CODE ###

def rt(i):
    while i!=G[i][0]:
        i = G[i][0]
    return i
N,M = map(int,input().split())
G = {i:[i,1] for i in range(1,N+1)}
for _ in range(M):
    X,Y,Z = map(int,input().split())
    rx = rt(X)
    ry = rt(Y)
    if rx!=ry:
        if G[rx][1]>=G[ry][1]:
            G[ry][0] = rx
            G[rx][1] += G[ry][1]
        else:
            G[rx][0] = ry
            G[ry][1] += G[rx][1]
cnt = 0
A = []
for i in range(1,N+1):
    A.append(rt(i))
A = list(set(A))
print(len(A))
### BUGGY CODE ###

import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

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

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

print(s % (10**9 + 7))
exit()


### FIXED CODE ###

import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

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

s = 0

S = [0]

for i in range(N):
    S.append(A[i] + S[i])

for i in range(N):
    s += A[i] * S[i]

print(s % (10**9 + 7))
exit()
### BUGGY CODE ###

# -*- conding:utf-8 -*-


from collections import deque

q_list = deque()
n = int(input())
tmp = [input().split() for i in range(n)]

for i in tmp:
    cmd, v = i
    if cmd == "find":
        if v in q_list:
            print("yes")
        else:
            print ("no")
    else:
        q_list.append(v)

### FIXED CODE ###

# -*- conding:utf-8 -*-


se = set()
n = int(input())
tmp = [input().split() for i in range(n)]


for i in tmp:
    cmd, v = i
    if cmd == "find":
        if v in se:
            print("yes")
        else:
            print ("no")
    else:
        se.add(v)
### BUGGY CODE ###

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
iro=[0]
iro[0]=a[0]
for i in range(1,n):
    iro.sort()
    flag=True
    for j in range(len(iro)-1):
        if a[i]>iro[j] and a[i]<=iro[j+1]:
            iro[j]=a[i]
            flag=False
    if a[i]>iro[-1]:
        iro[-1]=a[i]
        flag=False
    if flag:
        iro.append(a[i])
#print(iro)
print(len(iro))


### FIXED CODE ###

from bisect import bisect as br
n=int(input())
x=[-1]*n
for _ in range(n):
    a=int(input())
    i=br(x,a-1)-1
    x[i]=a
print(n-x.count(-1))
### BUGGY CODE ###

import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = np.zeros((len_s + 1, len_t + 1), dtype=np.int)
for index_s in range(len_s):
  char_s = s[index_s]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp[index_s + 1, index_t + 1] = dp[index_s, index_t] + 1
    else:
      dp[index_s + 1, index_t + 1] = max(
        dp[index_s, index_t + 1], dp[index_s + 1, index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp[-1, -1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s, index_t + 1] == len_lcs:
    index_s -= 1
  elif dp[index_s + 1, index_t] == len_lcs:
    index_t -= 1
  else:
    raise ValueError
print(''.join(lcs_reverse[::-1]))

### FIXED CODE ###

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))