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

import sys
sys.setrecursionlimit(100000000)
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
a = []
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    a.append(r-1)
    a.append(l-1)
    t = r-1

col = [ float("inf") for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == float("inf"):
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()


dfs(t,0)
a = list(set(a))
for i in a:
    if col[i] == float("inf"):
        dfs(i,0)


print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):

        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


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

N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
mod = 1000000007
dp=[0]*(N+1)
dp[0]=1
if M != 0:
    if A[0]!=1:
        dp[1]=1 
    else:
        dp[1]=0
else:
    dp[1]=1
    
for i in range(2,N+1):
    if i in A:
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[-1])

### FIXED CODE ###

mod = 10**9+7
n,m = map(int,input().split())
a = set()
for i in range(m):
  a.add(int(input()))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a :
        dp[i] = 0
print(dp[n])
### BUGGY CODE ###

n,m,q=map(int, input().split())
lr=[list(map(int,input().split())) for i in range(m)]
pq=[list(map(int,input().split())) for i in range(q)]

import numpy as np
a=np.zeros((n+1,n+1),dtype=int)
for i in range(m):
    a[lr[i][0]:,lr[i][1]:]+=1
for i in range(q):
    print(a[pq[i][1],pq[i][1]]-a[pq[i][0]-1,pq[i][1]])

### FIXED CODE ###

n,m,q=map(int, input().split())
lr=[list(map(int,input().split())) for i in range(m)]
pq=[list(map(int,input().split())) for i in range(q)]

a=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a[lr[i][0]][lr[i][1]]+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        a[i][j]+=a[i-1][j]
for i in range(1,n+1):
    for j in range(1,n+1):
        a[i][j]+=a[i][j-1]
for i in range(q):
    print(a[pq[i][1]][pq[i][1]]-a[pq[i][0]-1][pq[i][1]])
### BUGGY CODE ###

N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = map(int, input().split(" "))
    for j in range(b):
        Alist.append(c)

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

print(ans)

### FIXED CODE ###

N, M  = map(int, input().split(" "))
Alist = list(map(int, input().split(" ")))
bclist = []
leng = len(Alist)
ans = 0
#print(Alist)
for i in range(M):
    b, c = (map(int, input().split(" ")))
    bclist.append([c,b])
bclist.sort(reverse = True)
#print(bclist)

count = 0
for j in range(M):
    for n in range(bclist[j][1]):
        Alist.append(bclist[j][0])
    count += bclist[j][1]
    if count >= leng:
        break
    

Alist.sort()

for k in range(leng):
    ans += Alist[-k-1]

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

N = int(input())
s = [tuple(map(int, input().split())) for i in range(N)]

s.sort(key=lambda x: x[1])

t = list(map(lambda j:(j[0]-j[1]+1, j[0]+j[1]-1), s))
NN = len(t)
dobon = []

for k in range(NN):
  for l in range(k+1, NN):
    if l not in dobon:
      if int(t[k][1]) <= int(t[l][1]):
        if (t[l][0] <= t[k][1]) and (t[k][1] <= t[l][1]):
          N -= 1
          dobon.append(l)
          break
      else:
        if (t[l][0] <= t[k][0]) and (t[k][0] <= t[l][1]):
          N -= 1
          dobon.append(l)
          break

print(N)

### FIXED CODE ###

N = int(input())
S = [tuple(map(int, input().split())) for i in range(N)]
T = list(map(lambda j:(j[0]-j[1], j[0]+j[1]), S))

T.sort(key=lambda x: x[1])

for i, t in enumerate(T):
  if i>0:
    if end <= t[0]:
      res += 1
      start = t[0]
      end = t[1]
  else:
    start = t[0]
    end = t[1]
    res = 1

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

n = int(input())
Nr = list(reversed(list(map(int,str(n)))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if i<(10**100):
        if Nr[i] > 5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        elif Nr[i]==5:
            if Nr[i+1]>=5:
                Nr[i+1] += 1
                ans += (10 - Nr[i])
            else:
                ans += Nr[i]
        else:
            ans += Nr[i]
    elif i==(10**100):
        A = Nr[i:]
        B = list(map(str,A))
        C = "".join(B)
        D = int(C)
        ans += D
    else:
        break

print(ans)

### FIXED CODE ###

n = input()
Nr = list(map(int,list(reversed(n))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if Nr[i] > 5:
        Nr[i+1] += 1
        ans += (10 - Nr[i])
    elif Nr[i]==5:
        if Nr[i+1]>=5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        else:
            ans += Nr[i]
    else:
        ans += Nr[i]

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

import numpy as np
nkq = list(map(int, (input().split())))
ans = [int(input()) for i in range(nkq[2])]
hold_point = []
[hold_point.append(nkq[1]) for i in range(nkq[0])]
hold_point = np.array(hold_point)
for i in range(nkq[2]):
    hold_point = hold_point - 1
for i in ans:
    hold_point[i - 1] += 1
for i in hold_point:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
nkq = list(map(int, (input().split())))
ans = [int(input()) for i in range(nkq[2])]
total = nkq[1] - nkq[2]
hold_point = np.array([total]*nkq[0])
for i in ans:
    hold_point[i - 1] += 1
for i in hold_point:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

n_bit = max(a).bit_length()
b = [(1 << j) % MOD for j in range(n_bit)]

ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += b[j] * (i - bit[j])
            bit[j] += 1
        else:
            ans += b[j] * bit[j]
        ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

n_bit = max(a).bit_length()
b = [(1 << j) % MOD for j in range(n_bit)]

ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += b[j] * (i - bit[j])
            bit[j] += 1
        else:
            ans += b[j] * bit[j]
        ans %= MOD

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

n = int(input())
lis = str(input())
r = []
g = []
b = []
for i in range(n):
  if lis[i] == "R":
    r.append(i)
  elif lis[i] == "G":
    g.append(i)
  else:
    b.append(i)
ans = len(r) * len(g) * len(b)
for i in range(1,n-1):
  for j in range(i+1,n):
    if i != j and 2 * j -i <= n:
      k = j + (j-i)
      if (lis[i-1] != lis[j-1]) and (lis[j-1] != lis[k-1]) and (lis[k-1] != lis[i-1]):
        ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
lis = str(input())
r = []
g = []
b = []
for i in range(n):
  if lis[i] == "R":
    r.append(i)
  elif lis[i] == "G":
    g.append(i)
  else:
    b.append(i)
ans = len(r) * len(g) * len(b)
for i in range(1,n-1):
  for j in range(i+1,n):
    if i != j and 2 * j -i <= n:
      k = j + (j-i)
      if (lis[i-1] != lis[j-1]) and (lis[j-1] != lis[k-1]) and (lis[k-1] != lis[i-1]):
        ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())

# i = format(n, 'b')[::-1].find('1')
ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n == 1:
    break

print(ans+k)

### FIXED CODE ###

n = int(input())

# i = format(n, 'b')[::-1].find('1')
ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n == 1:
    print(ans+k)
    break
  elif n < 1:
    print(ans)
    break
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A.append(a)

print(len(A))

### FIXED CODE ###



N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

B = set()

for a in A:
    if a in B:
        B.remove(a)
    else:
        B.add(a)

print(len(B))
### BUGGY CODE ###

import itertools 

n = int(input())

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

cnt = 0
for a,b,c in itertools.combinations(L,3):
    if a >= b+c:
        continue
    if b >= a+c:
        continue
    if c >= a+b:
        continue
    
    cnt += 1

print(cnt)   


### FIXED CODE ###

import itertools
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

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

n,a=int(input()),list(map(int,input().split()));c=[0,0,0];x=[1.0/i for i in range(1,n+1)]
for i in a:c[i-1]+=1
dp=[[[-1]*(c[2]+2) for i in range(c[1]+c[2]+2)]for i in range(n+2)]
for k in range(c[2]+1):
  for j in range(c[2]+c[1]-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
a=A
num=B-A+1
while a<=B:
    if a%C==0:
        num=num-1
    elif a%D==0:
        num=num-1
    a=a+1
print(num)

### FIXED CODE ###

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

E = C*D//math.gcd(C,D)
all = B - A + 1
Cmod = B//C - (A-1)//C
Dmod = B//D - (A-1)//D
CDmod = B//E - (A-1)//E

print(all - Cmod - Dmod + CDmod)
### BUGGY CODE ###

N=int(input())
listA=list(map(int, input().split()))
Q=int(input())

listB=[] #appendのために宣言が必要
while True:
    try:
        listB.append(list(map(int,input().split())))

    except:
        break;

for i in range(Q):
  for j in range(len(listA)):
    if listA[j]==listB[i][0]:
      listA[j]=listB[i][1]
  #print(listA)
  print(sum(listA))

### FIXED CODE ###

N=int(input())
listA=list(map(int, input().split()))
Q=int(input())

listB=[] #appendのために宣言が必要
while True:
    try:
        listB.append(list(map(int,input().split())))

    except:
        break;
        
sum=sum(listA)
numlist=[0]*(10**5+1)
for i in listA:
  numlist[i]+=1
  
for i in range(Q):
  B=listB[i][0]
  C=listB[i][1]
  if numlist[B]!=0:
    sum=sum+(C-B)*numlist[B]
    # print(C)
    numlist[C]+=numlist[B]
    numlist[B]=0
    # print(numlist)
  print(sum)
### BUGGY CODE ###

from copy import copy

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

for xi in X:
    Y = copy(X)
    Y.remove(xi)
    print(sorted(Y)[N // 2 - 1])


### FIXED CODE ###

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

M_small = sorted(X)[N // 2 - 1]
M_large = sorted(X)[N // 2]

for xi in X:
    if xi <= M_small:
        print(M_large)
    else:
        print(M_small)
### BUGGY CODE ###

n=int(input())
emptylists=[]
for i in range(5):
    s=int(input())
    emptylists.append(s)
    
lists=[n,0,0,0,0,0]
cnt=0
while lists[5]<n:
    if lists[0]>0:
        which1=min(lists[0],emptylists[1])
    else:
        which1=0
        
    if lists[1]>0:
        whichi2=min(lists[1],emptylists[1])
    else:
        which2=0
        
    if lists[2]>0:
        which3=min(lists[2],emptylists[2])
    else:
        which3=0
        
    if lists[3]>0:
        which4=min(lists[3],emptylists[3])
    else:
        which4=0
        
        
    if lists[4]>0:
        which5=min(lists[4],emptylists[4])
    else:
        which5=0
        
    lists[0]=lists[0]-which1
    lists[1]=lists[1]+which1-which2
    lists[2]=lists[2]+which2-which3
    lists[3]=lists[3]+which3-which4
    lists[4]=lists[4]+which4-which5
    lists[5]=lists[5]+which5
    cnt+=1
print(cnt)

### FIXED CODE ###

import math
n=int(input())
lists=[]
for x in range(5):
    s=int(input())
    lists.append(s)
min_numbers=min(lists[:])
Nums=math.ceil(n/min_numbers)
print(Nums+4)
### BUGGY CODE ###

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

sum = 0
for i in range(N):
    for j in range(i+1, N):
        sum = sum + A[i]*A[j]
        if (sum > 10**9 + 7):
            sum = sum % (10**9 + 7)

print(sum)

### FIXED CODE ###

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

MOD = 10**9 + 7
sum_A = 0
for i in range(N):
    sum_A = (sum_A + A[i]) % MOD

sum = 0
for i in range(N):
    sum_A = (sum_A - A[i]) % MOD
    sum = (sum + sum_A*A[i]) % MOD 


print(sum)
### BUGGY CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):

  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][((j*10)%13+k)%13]+=dp[i][j]%MOD
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][((j*10)%13+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)

### FIXED CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)
### BUGGY CODE ###

n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

s,t=map(int,input().split())
s,t=s-1,t-1
s,t=3*s,3*t

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[] and flag==0:
     que2=[]
     cnt+=1
     for i in que:
          if flag==1:
               break
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

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

# @functools.lru_cache(None)
# def dp(i,j):
#     if i == j: return 0
#     if (N % 2 == 0 and (j - i) % 2 == 0) or (N % 2 == 1 and (j - i) % 2 == 1):
#         return max(dp(i+1,j) + a[i], dp(i,j-1) + a[j-1])
#     else:
#         return min(dp(i+1,j) - a[i], dp(i,j-1) - a[j-1])
#
# print(dp(1,N+1))

@functools.lru_cache(None)
def f(l,r):
    if l==r: return a[l]
    return max(a[l] - f(l+1,r), a[r]-f(l,r-1))

print(f(1,N))

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

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

dp = [[0]*(N+5) for i in range(N+5)]

for k in range(1,N+1):
    for l in range(1,N+2-k):
        r = l + k
        if (N-k) % 2 == 0:
            dp[l][r] = max(dp[l+1][r] + a[l], dp[l][r-1] + a[r-1])
        else:
            dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

print(dp[1][N+1])
### BUGGY CODE ###

from collections import defaultdict as dd
h, w, m = map(int, input().split())

#dic[row, col] -> set(ids)
h_dic = dd(set)
w_dic = dd(set)
spot = set()

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c].add(i)
    w_dic[w_c].add(i)
    spot.add((h_c, w_c))
#print(h_dic, w_dic)

#H_lis -> [i, num_spot(int)]
max_h_num = 0
H_lis = []
for key, val in h_dic.items():
    H_lis.append([key, len(val)])
    max_h_num = max(max_h_num, len(val))
max_w_num = 0
W_lis = []
for key, val in w_dic.items():
    W_lis.append([key, len(val)])
    max_w_num = max(max_w_num, len(val))


#print(H_lis, W_lis)
#print(max_h)

ans = 0
max_h_lis = [val[0] for val in H_lis if val[1] == max_h_num]
max_w_lis = [val[0] for val in W_lis if val[1] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        count = max_h_num + max_w_num
        if (i, j) in spot:
            count -= 1
        ans = max(ans, count)
print(ans)

"""    
max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

"""

### FIXED CODE ###

from sys import exit
from collections import defaultdict as dd
h, w, m = map(int, input().split())

#dic[row, col] -> set(ids)
h_dic = dd(int)
w_dic = dd(int)
spot = set()

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c] += 1
    w_dic[w_c] += 1
    spot.add((h_c, w_c))
#print(h_dic, w_dic)

#H_lis -> [i, num_spot(int)]
max_h_num = 0
for key, val in h_dic.items():
    max_h_num = max(max_h_num, val)
max_w_num = 0
W_lis = []
for key, val in w_dic.items():
    max_w_num = max(max_w_num, val)


#print(H_lis, W_lis)
#print(max_h)

ans = 0
max_h_lis = [key for key in h_dic if h_dic[key] == max_h_num]
max_w_lis = [key for key in w_dic if w_dic[key] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        if (i, j) not in spot:
            print(max_h_num + max_w_num)
            exit()
else:
    print(max_h_num + max_w_num - 1)

"""    
max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

"""
### BUGGY CODE ###

import itertools

s=input()
K=int(input())

dic=[]

for i in range(1,6):
    for k in itertools.permutations('abcdefghijklmnopqrstuvwxyz', i):
        dic.append(''.join(k))
dic.sort()


ans=0
for str in dic:
    if str in s:
        ans+=1
    if ans==K:
        print(str)
        exit()

### FIXED CODE ###

s=input()
K=int(input())
st=set()

for i in range(len(s)):
    for j in range(1,6):
        st.add(s[i:i+j])

sl=sorted(list(st))

print(sl[K-1])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
answer = 0
for i in range(N - K + 1):
    t = 0
    for j in range(i, i + K):
        j = P[j]
        t += (j * (j + 1) / 2) / j
    answer = max(answer, t)
print(answer)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
t = [0] * 1000000
for i in range(N):
    t[i + 1] = t[i] + P[i] + 1
ans = 0
for i in range(N - K + 1):
    ans = max(ans, t[i+K] - t[i])
print(ans / 2)
### BUGGY CODE ###

m, n = map(int, input().split())
print(m**n % 1000000007)


### FIXED CODE ###

m, n = map(int, input().split())
print(pow(m, n, 1000000007))
### BUGGY CODE ###

n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
used=[False for _ in range(n)]
linked=[[] for _ in range(n)]

for i in range(n):
    dist[i][i]=0

for i in range(n-1):
    a,b,c=map(int,input().split())
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c
    linked[a-1].append(b-1)
    linked[b-1].append(a-1)

def dfs(v,dv):
    d[v]=dv
    used[v]=True
    for i in linked[v]:
        linked[i].remove(v)
        if(used[i]):
            continue
        dfs(i,dv+dist[v][i])



q,k=map(int,input().split())

dfs(k-1,0)

for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
g=[[] for _ in range(n)]


for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])

def dfs(v,p,dv):
    d[v]=dv
    for gi,c in g[v]:
        if(gi==p):
            continue
        dfs(gi,v,dv+c)

q,k=map(int,input().split())

dfs(k-1,-1,0)

for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

n = int(input())
s = input()

c = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        for k in range(j+1, n):
            if s[i] == s[k] or s[j] == s[k]:
                continue

            if j - i != k - j:
                c += 1

print(c)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
s = input()

rgb = {'R': 0, 'G': 0, 'B': 0}
for i in s:
    rgb[i] += 1

c = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k and k < n and s[i] != s[k] and s[j] != s[k]:
                c += 1

print(rgb['R']*rgb['G']*rgb['B'] - c)
### BUGGY CODE ###

def main():
  X = input()

  st = "ST"
  con = X.count(st)
  
  while con > 0:
    X = X.replace(st,"")
    con = X.count(st)
    
  print(len(X))
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import deque

X = input()
N = len(X)
S = "S"
T = "T"
stack = deque("")

for i,str in enumerate(X):
  if str == S:
    stack.append(str)
  elif str == T:
    if len(stack) == 0:
      stack.append(str)
    elif stack[-1] == T:
      stack.append(str)
    elif stack[-1] == S:
      stack.pop()
      
print(len(stack))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [0 for _ in range(N)]
    for i in range(N):
        A = int(input())
        ind[A-1] = i

    ans = 0
    count = 0
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            count += 1
        else:
            ans = max(ans,count)
            count = 0
        ans = max(ans,count)

    print(N-ans-1) 

if __name__ == "__main__":
    main()