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

n = int(input())
list = input().split()
 
int_list = [ int(n) for n in list ]
 
isDist = True
 
for a in range(n):
  x = a+1
  if int_list[a] in int_list[x:]:
    print("NO")
    isDist = False
    break;
 
if isDist is True:
    print("YES")

### FIXED CODE ###

n = int(input())
list = input().split()
 
int_list = [ int(n) for n in list ]
int_list.sort()

isDist = True
 
for a in range(n-1):
  if int_list[a] == int_list[a+1]:
    print("NO")
    isDist = False
    break;
 
if isDist is True:
    print("YES")
### BUGGY CODE ###

n,k = map(int,input().split());
i = 0;
while True:
    if (n - i)% k == 0:
        break;
    if (n + i)% k == 0:
        break;
    i += 1;

print(i);

### FIXED CODE ###

n,k = map(int,input().split());
i = 0;
if n == k:
    print(0);
elif n < k:
    print(min(n,k-n));
else:
    v = (n - k)%k;
    if v*2 >= k:
        print(k-v);
    else:
        print(v);
### BUGGY CODE ###

from string import ascii_lowercase


def main():
    s = input()
    t = input()
    s_all = {s: 0 for s in ascii_lowercase}
    for ss in s:
        s_all[ss] += 1
    ans = 0
    if any(s_all[tt] == 0 for tt in t):
        ans = -1
    else:
        s_ind = -1
        rest = 0
        for i in range(len(t)):
            while True:
                s_ind += 1
                if s_ind == len(s):
                    s_ind = 0
                    ans += 1
                if s[s_ind] == t[i]:
                    rest = s_ind + 1
                    break
        ans *= len(s)
        ans += rest
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from string import ascii_lowercase
from bisect import bisect_right, bisect_left


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i + 1)
    ans = 0
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 1
        for ss in ascii_lowercase:
            s_all[ss].sort()
        for i in range(len(t)):
            next_ind = bisect_left(s_all[t[i]], s_ind)
            if next_ind == len(s_all[t[i]]):
                ans += len_s - s_ind + 1
                ans += s_all[t[i]][0]
                s_ind = s_all[t[i]][0] + 1
            else:
                ans += s_all[t[i]][next_ind] - s_ind + 1
                s_ind = s_all[t[i]][next_ind] + 1
    print(ans)


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

from operator import itemgetter
import sys

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の３つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

e = []
for i in range(n):
    e.append([i,a[i]/b[i],a[i],b[i]])

e.sort(key=itemgetter(1),reverse=True)
mea = e[0][1]
asum = 0
bsum = 0
min_bsum = 9999999999999999999

path = [0]*(10**4+1)
#path = [0]*(40)

depth = 0
while 1:
    #攻撃番号を得る
    anum = path[depth]

    #有効な攻撃か確認
    if anum > n-1:
        #攻撃ネタ切れなので１つ戻る
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue

    #攻撃実施
    asum = asum + e[anum][2]
    bsum = bsum + e[anum][3]
#    print("途中",h,asum,bsum,min_bsum,path[:depth])

    #攻撃後の状況チェック
    if asum >= h:
        if bsum < min_bsum:
            min_bsum = bsum
            #print("min更新",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
#    elif bsum >= min_bsum:    #積めないので 次の攻撃に行く
    elif (h-asum)/mea + bsum >= min_bsum:    #最大効率で積んだとしてオーバーなので次の攻撃に行く
        #print("オーバー",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        '''
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue
        '''
        continue
    else:
        depth += 1

print(min_bsum)

### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

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

d = 0
c = []
for b in range(-max(a),min(a)+1):
    for i in range(0,len(a)):
        d += abs(a[i]-(b+i+1))
    c.append(d)
    d = 0
print(min(c))

### FIXED CODE ###

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

b_l = []
for i in range(0,len(a)):
    b_l.append(a[i] - (i+1))
b_l.sort()
b = b_l[n//2]
ans = 0
for i in range(0,len(a)):
    ans += abs(a[i] - (i+1+b))
print(ans)
### BUGGY CODE ###

a,b,x = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    if i%x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

def f(n,d):
    if n==-1:
        return 0
    return n//d+1

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

class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = n
        m = 1 << ((n + 1).bit_length() + 1)
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, n, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))


### FIXED CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]

x_cost = [[0 for _ in range(N)] for _ in range(1 << N)]
y_cost = [[0 for _ in range(N)] for _ in range(1 << N)]

for bit in range(1 << N):
    for i in range(N):
        x_cost[bit][i] = abs(XYP[i][0])
        y_cost[bit][i] = abs(XYP[i][1])

        for k in range(N):
            if bit & (1 << k):
                x_cost[bit][i] = min(x_cost[bit][i], abs(XYP[i][0] - XYP[k][0]))
                y_cost[bit][i] = min(y_cost[bit][i], abs(XYP[i][1] - XYP[k][1]))

ans = [sys.maxsize for _ in range(N + 1)]

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        for k in range(N):
            cost += 1 * XYP[k][2] * min(x_cost[bit_][k], y_cost[bit - bit_][k])
        ans[cnt] = min(ans[cnt], cost)

        bit_ -= 1
for i in range(N + 1):
    print(ans[i])

### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

X = int(readline())

if X <= 599:
    print(8)
elif X <= 799:
    print(7)
elif X <= 999:
    print(6)
elif X <= 1199:
    print(5)
elif X <= 1399:
    print(4)
elif X <= 1599:
    print(3)
elif X <= 1799:
    print(2)
elif X <= 1999:
    print(1)
### BUGGY CODE ###

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

from math import log10

total=1
for i in range(n):
    total*=a[i]

def pows(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
    x = x*x
    n = n >> 1 #ビットシフト
  return ans

a= pows(10,18)

if total-a>0:
    print(-1)
else:
    print(total)

### FIXED CODE ###

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

if a.count(0)>0:
    print(0)
    exit(0)

total=1
for i in a:
    total *=i

    if total>10**18:
        print(-1)
        exit(0)
    
print(total)
### BUGGY CODE ###

n = int(input())
ip = []

for i in range(n):
  a = int(input())
  ip.append(a)
  for j in range(a):
    x,y = map(int,input().split())
    ip.append([x,y])

max = 0    
for i in range(n) :
  max += 2**i

ans = 0
for i in range(0,max+1) :
  s = [2 for _ in range(n)]
  bit = i
  count = 0
  index = 0
  check = 0
  for j in range(n) :
    if bit%2 == 1 :
      if s[j] == 0 :
        check = 1
      s[j] = 1
    else :
      if s[j] == 1 :
        check = 1
      s[j] = 0
    bit = bit//2
    for k in range(ip[index]) :
      if s[j] == 1 :
        if ip[index+1+k][1] == 1 :
          if s[ip[index+1+k][0]-1] == 0 :
            check = 1
          s[ip[index+1+k][0]-1] = 1
        elif ip[index+1+k][1] == 0 :
          if s[ip[index+1+k][0]-1] == 1 :
            check = 1
          s[ip[index+1+k][0]-1] = 0
    index += ip[index] + 1
  if ans < s.count(1) and check ==0 :
    ans = s.count(1)

print(ans)

### FIXED CODE ###

n = int(input())
ip = []

for i in range(n):
  a = int(input())
  ip.append(a)
  for j in range(a):
    x,y = map(int,input().split())
    ip.append([x,y])

max = 0    
for i in range(n) :
  max += 2**i

ans = 0
for i in range(0,max+1) :
  s = [2 for _ in range(n)]
  bit = i
  count = 0
  index = 0
  check = 0
  for j in range(n) :
    if bit%2 == 1 :
      if s[j] == 0 :
        check = 1
        break
      s[j] = 1
    else :
      if s[j] == 1 :
        check = 1
        break
      s[j] = 0
    bit = bit//2
    for k in range(ip[index]) :
      if s[j] == 1 :
        if ip[index+1+k][1] == 1 :
          if s[ip[index+1+k][0]-1] == 0 :
            check = 1
            break
          s[ip[index+1+k][0]-1] = 1
        elif ip[index+1+k][1] == 0 :
          if s[ip[index+1+k][0]-1] == 1 :
            check = 1
            break
          s[ip[index+1+k][0]-1] = 0
    if check == 1 :
      break
    index += ip[index] + 1
  if ans < s.count(1) and check ==0 :
    ans = s.count(1)

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

N,K = map(int, input().split(' '))
A = [int(i) for i in input().split(' ')]

num = []
count = []
for a in range(len(A)):
    tmp = A[a]
    if not tmp in num:
        num.append(tmp)
        count.append(1)
    else:
        index = num.index(tmp)
        count[index] += 1

count = sorted(count)
ans = 0
if len(count)<=K:
    pass
else:
    for i in range(len(count)-K):
        ans += count[i]

print(ans)

### FIXED CODE ###

#辞書型でリトライ
N,K = map(int, input().split(' '))
A = input().split(' ')

dic = {}
for a in range(len(A)):
    tmp = A[a]
    if not tmp in dic:
        dic[tmp] = 1
    else:
        dic[tmp] += 1

values = sorted(dic.values())
ans = 0
if len(values)<=K:
    pass
else:
    tmp = len(values)-K
    values = values[:tmp]
    ans = sum(values)

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

n = int(input())
a = [int(input()) for _ in range(n)]
s = max(a)
for i in range(n):
  if a[i] == s:
    l = a.copy()
    l[i] = 0
    print(max(l))
  else:
    print(s)



  

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
s = max(a)
if a.count(s) >= 2:
  for i in range(n):  
    print(s)
else:
  for i in range(n):
    if a[i] == s:
      l = a.copy()
      l.sort()
      print(l[-2])
    else:
      print(s)
### BUGGY CODE ###

import itertools

maxnum=0

def parm_check(n,maxnum):
    if(n >= 2):
        #print(tmp)
        #print(list(itertools.combinations(a,n)))
        comb = list(itertools.combinations(a,n))
        for j in range(len(comb)):
            if(sum(comb[j]) % 10 != 0 and maxnum < sum(comb[j])):
                maxnum = sum(comb[j])
    else:
        for j in range(N):
            #print(tmp[j])
            if(a[j] % 10 != 0 and maxnum < a[j]):
                maxnum=a[j]
    
    return maxnum

if(__name__=="__main__"):
    N = int(input())
    a =[int(input()) for i in range(N)]
    #print(sum(a))
    
    if(sum(a) % 10 != 0):
        print(sum(a))
    else:
        for i in range(N-1,1,-1):
            maxnum = parm_check(i,maxnum)
            if(maxnum != 0):
                break

        print(maxnum)


### FIXED CODE ###

maxnum=0

if(__name__=="__main__"):
    N = int(input())
    a =[int(input()) for i in range(N)]
    #print(sum(a))
    
    if(sum(a) % 10 != 0):
        print(sum(a))
    else:
        a_sort = sorted(a)
        for i in range(0,N):
            if(a_sort[i] % 10 != 0):
                del a_sort[i]
                maxnum = sum(a_sort)
                break
            

        print(maxnum)
### BUGGY CODE ###


import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, c):
    cnt[v]+=c
    for next_v in g[v]:
        if next_v == p:
            continue
        dfs(next_v, v, cnt[v])

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

g = [[] for _ in range(N)]
cnt = [0 for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p]+=x


dfs(0, -1, 0)

print(*cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

dfs(1, -1)

print(*list(cnt.values())[1:])
### BUGGY CODE ###

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

length = len(A)
head = 0
i = 1

while True:
    if i in A:
        head = A.index(i)
        A = A[head:]
        i += 1
    else:
        break

if i == 1:
    print(-1)
else:
    print(length - i + 1)


### FIXED CODE ###

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

length = len(A)
find_next = 1

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

if find_next == 1:
    print(-1)
else:
    print(length - find_next + 1)
### BUGGY CODE ###

import sys

A = list(map(int, sys.stdin.read().rstrip().split("\n")))
n = A[0]
del A[0]

#shellSort
cnt = 0

G = []
tg = 1
while tg <= n:
    G.append(tg)
    tg = 3 * tg + 1
G.reverse()

m = len(G)

for i in range(m):
    g = G[i]
    # insertionSort
    for j in range(g, n):
        k = j - g
        while (k >= 0) and (A[k] > A[k + g]):
            A[k + g], A[k] = A[k], A[k + g]
            k -= g
            cnt += 1

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))

### FIXED CODE ###

import sys

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0) and (A[j] > v):
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v

def shellSort(A, n):
    G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m = len(G)
    for k in range(m):
        insertionSort(A, n, G[k])
    return m, G

A = list(map(int, sys.stdin))
n = A[0]
del A[0]

cnt = 0

m, G = shellSort(A, n)

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()

ansLis = [0]
line = ""
for i in range(N):
    line += S[i]
    ansLis.append(line.count("AC"))
# print(ansLis)

ans = []
for _ in range(Q):
    l,r = map(int,input().split())
    num = ansLis[r] - ansLis[l]
    # if S[l-2] == "A" and S[l-1] == "C":
    #     num = max(0, num-1)
    ans.append(num)

print(*ans,sep="\n")

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()

ansLis = [0]
tmp = 0
flgA = False
for i in range(N):
    if flgA and S[i]=="C":
        tmp += 1
    ansLis.append(tmp)
    flgA = (S[i] == "A")
# print(ansLis)

ans = []
for _ in range(Q):
    l,r = map(int,input().split())
    num = ansLis[r] - ansLis[l]
    # if S[l-2] == "A" and S[l-1] == "C":
    #     num = max(0, num-1)
    ans.append(num)

print(*ans,sep="\n")
### BUGGY CODE ###

H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
A=0
for h in range(H):
    for w in range(W):
        a=ans[h][w]
        if a!="#":
            A=max(A, a)
print(A)


### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



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

import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())
a = deque(lst[:n])
b = lst[n:]
for k in range(n):
    tmp = a[0] ^ b[0]
    for ai, bi in zip(a, b):
        if ai ^ bi != tmp:
            break
    else:
        print(k, tmp)
    a.rotate(-1)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

def cal_ans(x):
    ans = (x*(x+1)/2)/x
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p =  list(map(cal_ans,p))

ans_temp = 0
ans_list = []
for i in range(n):
    try:
        if ans_temp < sum(p[i:i+k]):
            ans_temp = sum(p[i:i+k])
            ans_list = p[i:i+k]
    except:
        pass
print(ans_temp)

### FIXED CODE ###

# import numpy as np

def cal_ans(x):
    ans = (x+1)/2
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(cal_ans,p))

ans_temp = 0
ans_list = []
S = [0]
for i in range(n):
    S.append(S[i]+p[i])
# print(p)
# print(S)
# for i in range(n-k+1):
#     ans_list.append(sum(p[i:i+k]))
t_len = len(S)
ans1 = 0
for i in range(t_len - k):
    if ans1 < S[i+k]-S[i]:
        ans1 = S[i+k]-S[i]
print(ans1)
# ans = 0
# for i in range(k):
#     ans += (ans_list[i]*(ans_list[i]+1)/2)/ans_list[i]
#     # print((ans_list[i]*(ans_list[i]+1)/2))
# print(ans)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf')  for i in range(n) ]

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])