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

from collections import deque
import bisect
from copy import copy

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

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

d= deque()
INF=10010001001
dpinit = [a[0]]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.popleft()
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        if idx<len(dp):
            prv=dp[idx]
            dp[idx]=a[v]       
        else:
            dp.append(a[v])
            prv=-1
        ansls[v]=len(dp)
        d.append((v,u,copy(dp)))
        if prv!=-1:
            dp[idx]=prv
        else:
            dp.pop()


print(*ansls,sep='\n')

### FIXED CODE ###

from collections import deque
import bisect
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

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

INF=1001001001
dp = [INF]*n
dp[0]=a[0]
ansls=[0]*n
ansls[0]=1
history=deque()
def dfs(u,p,rank):
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        prv=dp[idx]
        dp[idx]=a[v]       
        history.append((idx,prv))
        ansls[v]=bisect.bisect_left(dp,INF)
        dfs(v,u,rank+1)
        while len(history)>rank:
            idx,prv =history.pop()
            dp[idx] = prv

dfs(0,-1,0)

print(*ansls,sep='\n')
### BUGGY CODE ###

#D - Dice in Line
N,K = map(int,input().split())
p = list(map(int, input().split()))
sum = 0
sum_t = 0
for i in range(N-K+1):
    sum_t = 0
    for j in range(i, i+K):
        sum_t += ((1+p[j])*p[j])/(2*p[j])

    if sum_t >= sum:
        sum = sum_t
    else:
        pass

print(sum)

### FIXED CODE ###

#D - Dice in Line
N,K = map(int,input().split())
p = list(map(int, input().split()))
S = [0]*N
s = 0
s_t = 0
S[0] = (1+p[0])/2

if N == 1:
    print(S[0])
    exit()
else:
    pass

for i in range(N-1):
    S[i+1] =S[i]+(1+p[i+1])/2

if N == K:
    print(S[N-1])
    exit()
else:
    pass

for j in range(N-K):
    s_t = S[j+K]-S[j]
    if s_t >= s:
        s = s_t
    else:
        pass

print(s)
### BUGGY CODE ###

A, B, K = map(int, input().split())

nums = [x for x in range(A, B+1)]
ans = set()
for i in range(0, K):
    if i >= len(nums):
        break
    ans.add(nums[i])

for i in range(len(nums)-K, len(nums)):
    if i < 0:
        break
    ans.add(nums[i])

for n in sorted(list(ans)):
    print(n)

### FIXED CODE ###

A, B, K = map(int, input().split())

if B-A+1 < 2*K:
   for x in range(A, B+1):
      print(x)
else:
    for x in range(A, A+K):
        print(x)
    for x in range(B-K+1, B+1):
        print(x)
### BUGGY CODE ###

from heapq import *
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = [((0, 0), x1-1, y1-1, i) for i in range(4)]
while q:
    count, x, y, d = heappop(q)
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] > nextcount:
                dp[x+dx][y+dy][dd] = nextcount
                heappush(q, (nextcount, x+dx, y+dy, dd))

ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
r, g, b = sorted([r, g, b], reverse=True)
cnt = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        rg = r*i + g*j
        k = (n-rg)//b
        if k >= 0 and i+j+k >= 1 and rg+b*k == n:
            cnt += 1
print(cnt) 

### FIXED CODE ###

r, g, b, n = map(int, input().split())
r, g, b = sorted([r, g, b], reverse=True)
cnt = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        rg = r*i + g*j
        k = (n-rg)//b
        if k >= 0 and i+j+k >= 1 and rg+b*k == n:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import itertools

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

comb = []
if K % 2 != 0:
    for a, b, c in itertools.product(range(1, N//K+1), range(1, N//K+1), range(1, N//K+1)):
        # print('odd:', a*K, b*K, c*K)
        comb.append((a, b, c))
else:
    for a, b, c in itertools.product(range(1, N//K+1), range(1, N//K+1), range(1, N//K+1)):
        # print('even_1:', a*K, b*K, c*K)
        comb.append((a, K, b, K, c, K))
    for a, b, c in itertools.product(range(1, (2*N+K)//(2*K)+1), range(1, (2*N+K)//(2*K)+1), range(1, (2*N+K)//(2*K)+1)):
        # print('even_2:', a*K-K//2, b*K-K//2, c*K-K//2)
        comb.append((a, K, 1, b, K, 1, c, K, 1))


print(len(set(comb)))


### FIXED CODE ###

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

if K % 2 == 0:
    ans = (N//K)**3 + ((N+K//2)//K)**3
else:
    ans = (N//K)**3
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
xn = list(map(int, input().split()))
xn_sorted = sorted(xn)

for xi in xn:
    xn_tmp = list(xn_sorted)
    xn_tmp.remove(xi)
    print(xn_tmp[(len(xn_tmp)+1)//2 -1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
xn = list(map(int, input().split()))
xn_sorted = sorted(xn)
val_a = xn_sorted[(len(xn_sorted))//2 - 1]
val_b = xn_sorted[(len(xn_sorted))//2]

for xi in xn:
    if xi <= val_a:
        print(val_b)
    else:
        print(val_a)
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, L = map(int, input().split())
    dic = defaultdict(int)
    for _ in range(N):
        s = input().rstrip('\n')
        s = [si for si in s]
        for i in range(len(s)):
            dic[''.join(s)] = 1
            s.pop()

    g = 0
    key = list(dic.keys())
    for s in key:
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if not dic[t]:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


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

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
ans=1
i=0
while(1):
    if a[i]==2:
        print(ans)
        exit()
    elif a[i]==1:
        print(-1)
        exit()
    else:
        i=a[i]-1
        ans+=1

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
b=[]
while(1):
    if ans==n:
        print(-1)
        exit()
    elif a[i]==1:
        print(ans)
        exit()
    else:
        ans+=1
        i=a[i]
### BUGGY CODE ###

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

ans = s[n-1]

def f(k, c):
    p = [0] * n
    a = n-1-k*c
    b = a - c
    #print(k, c, a, b)
    temp = 0
    while 0 <= temp <= n-1:
        if p[temp] == 1:
            return -1
        p[temp] = 1
        temp += a
        if p[temp] == 1:
            return -1
        p[temp] = 1
        if temp > n-1:
            return -1
        elif temp == n-1:
            return 0
        temp -= b
    return -1

for c in range(1, n-1):
    dp = s[n-1]
    for k in range(n-1):
        if (k+1) * c >= n-1:
            break
        else:
            dp += s[n - 1 - k * c] + s[k * c]
            if dp > ans:
                #print(k, c, dp, ans, 'dp')
                if f(k, c) == 0:
                    ans = dp

print(ans)


### FIXED CODE ###

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

ans = 0

for d in range(1, n):
    temp = 0
    L = 0
    R = n-1
    if (n-1) % d == 0:
        while L < R:
            temp += s[L] + s[R]
            ans = max(ans, temp)
            L += d
            R -= d
    else:
        while L + d < n-1:
            temp += s[L] + s[R]
            ans = max(ans, temp)
            L += d
            R -= d

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

from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([Node(i) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  total_done_set = set()

  def dfs(node, done_set):
    if node.id in done_set: return 0

    total_done_set.add(node.id)
    done_set.add(node.id)

    for child in node.children:
      node.size += dfs(child, done_set)

    return node.size


  ans_list = [0] * n

  def dfs2(node, done_set, connected_ids, total_len):
    node_id = node.id
    if node_id in done_set: return 0

    done_set.add(node_id)

    ans_list[node_id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    except_num = 0

    for child in node.children:
      if child.id not in node.block_id_set:
        except_num += 1

      dfs2(child, done_set, connected_ids, total_len)

    ans_list[node_id] -= except_num


  for base_node in nodes:
    if base_node.id not in total_done_set:
      done_set = set()
      dfs(base_node, done_set)
      dfs2(base_node, set(), done_set, len(done_set))

  print(*ans_list, sep=" ")


main()


### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([([], set()) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a][0].append(b)
    nodes[b][0].append(a)

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c][1].add(d)
    nodes[d][1].add(c)

  total_done_set = set()

  def dfs(node_id, done_set):
    if node_id in done_set: return 0

    total_done_set.add(node_id)
    done_set.add(node_id)

    size = 1
    for child_id in nodes[node_id][0]:
      size += dfs(child_id, done_set)

    return size


  ans_list = [-1] * n

  def dfs2(node_id, connected_ids, total_len):
    children, block_id_set = nodes[node_id]
    ans_list[node_id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids, block_id_set
    ))) - 1

    except_num = 0
    for child_id in children:
      if child_id not in block_id_set:
        except_num += 1

      if ans_list[child_id] == -1:
        dfs2(child_id, connected_ids, total_len)

    ans_list[node_id] -= except_num


  for i in range(n):
    if i not in total_done_set:
      done_set = set()
      dfs(i, done_set)
      dfs2(i, done_set, len(done_set))

  print(*ans_list, sep=" ")


main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
max_len = len(format(max(a), "b"))
b = [0 for _ in range(max_len)]

for i in range(n):
    count = 0
    while a[i] > 0:
        b[count] += a[i]%2
        a[i] //= 2
        count += 1

result = 0
for i in range(max_len):
    r = b[i]*(n-b[i])%mod
    r = (r*2**i) %mod
    result += r
print(result%mod) 

### FIXED CODE ###

import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
s = [list(map(int,input().split())) for l in range(N)]
ans = []
s.sort(key = lambda x:x[1],reverse = True)
cnt = {}
A = 0
for i in range(K):
    if s[i][0] not in cnt:
        cnt[s[i][0]] = 1
    else:
        cnt[s[i][0]] += 1
    ans.append(s[i])
    A += s[i][1]
A += len(cnt)**2

ans.sort(key = lambda x:x[1])
for i in range(K,N):
    if s[i][0] not in cnt:
        for j in range(K):
            if cnt[ans[j][0]] >= 2:
                ans.pop(j)
                ans.insert(0,s[i])
                cnt[s[i][0]] = 1
                temp = 0
                for l in ans:
                    temp += l[1]
                A = max(A,temp+len(cnt)**2)
                    
                break
            
            
    else:
        continue

    if len(cnt) >= K:break
print(A)

### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
 
# print(TD)
 
xs = sorted(TD, key=lambda x:-x[1])
 
#print(xs)
 
baset = 0
ts = set()
ds = []
 
for t, d in xs[:K]:
    baset += d
    if not t in ts:
        ts.add(t)
    else:
        ds.append(d)
result = baset + len(ts)**2
r = result

for t, d in xs[K:]:
    if not ds:
        break
    if t not in ts:
        r += 2*len(ts) + 1
        r += d - ds.pop()
        ts.add(t)
        result = max(r,result)

print(result)
### BUGGY CODE ###


import sys


def solv(n):
    r = 0
    if n % 2 == 1:
#        if (n-2) in primes:
        if binary_search(primes, n-2):
            r = 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
#            if q in primes:
            if binary_search(primes, q):
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


def binary_search(lis, x):
    if len(lis) == 0:
        return None
    i = len(lis) / 2
    if lis[i] == x:
        return x
    elif x < lis[i]:
        return binary_search(lis[:i], x)
    else:
        return binary_search(lis[i+1:], x)


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

### FIXED CODE ###


import sys
import itertools


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = []
for p in prime_list(50000):
    primes.append(p)
c = [0] * 50001 * 2
for i, j in itertools.combinations(primes, 2):
    c[i+j] += 1
for i in primes:
    c[i+i] += 1
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print c[n]
### BUGGY CODE ###

def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

    es = [[] for _ in range(N)]
    for u,v,a,b in UVAB:
        u,v = u-1,v-1
        es[u].append((v,a,b))
        es[v].append((u,a,b))

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

    es = [[] for _ in range(N)]
    for u,v,a,b in UVAB:
        u,v = u-1,v-1
        es[u].append((v,a,b))
        es[v].append((u,a,b))

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: break
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()
### BUGGY CODE ###

N, K   = map(int, input().split())
L = list(map(int, input().split()))
L.append(0)
L.sort()
dis = []
for i in range(N-K+1):
    if 0 in L[i:i+K+1]:
        l = L[i:i+K+1]
              
        d = abs(l[0]) + abs(l[-1])*2
        dis.append(d)
        d = abs(l[0])*2 + abs(l[-1])
        dis.append(d)
print(min(dis))


### FIXED CODE ###

N, K  = map(int,input().split())
L =list(map(int,input().split()))
Lzero = list(filter(lambda x:x==0,L))
Lright = list(filter(lambda x:x>0,L))
Lleft = list(map(lambda x:abs(x),filter(lambda x:x<0,L)))[::-1]
K -= len(Lzero)
if K <= 0:
    print(0)
    quit()

dis = []
if len(Lright) == 0:
    print(Lleft[K-1])
    quit()
if len(Lleft) == 0:
    print(Lright[K-1])
    quit()
try :
    dis.append(Lright[K-1])
    dis.append(Lleft[K-1])
except:
    pass


for i in range(len(Lright)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lright[i])
        break
    d = 2*Lright[i]
    remain -= (i+1)
    try :
        d += Lleft[remain-1]
        dis.append(d)
    except:
        pass
for i in range(len(Lleft)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lleft[i])
        break
    d = 2*Lleft[i]
    remain -= (i+1)
    try:
        d += Lright[remain-1]
        dis.append(d)
    except:
        pass
print(min(dis))