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

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A.values()):
                print(-1)
                return
            else:
                raise ValueError("test")
        # print("11111")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if all(len(a) == 0 for a in A.values()):
            print(count)
            return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            # if target < i:
            #     continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print(-1)
                return
            else:
                raise ValueError("test")

        qq = []
        for i in set(pool):
            A[i].pop()
            if len(A[i]) != 0:
                qq.append(i)
        Q = set(qq)

        count += 1
        if len(Q) == 0:
            print(count)
            return


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

import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    minstop = 10**9 + 1

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
            if e.pos < minstop:
                minstop = e.pos
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown state
        else: #evaluate
            if minstop == -1 or minstop == 10**9 + 1:
                if len(s_stop) != 0:
                    minstop = min(s_stop)
                    ans[e.idx] = minstop
            else:
                ans[e.idx] = minstop

    print("\n".join(map(str, ans)))

solve()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

while True:
    n = input()
    if n == 0: break
    ans = [0,0,0,0,0,0,0]
    for i in xrange(n):
        age = input()
        if age <= 9:
            ans[0] += 1
        elif age <= 19:
            ans[1] += 1
        elif age <= 29:
            ans[2] += 1
        elif age <= 39:
            ans[3] += 1
        elif age <= 49:
            ans[4] += 1
        elif age <= 59:
            ans[5] += 1
        else:
            ans[6] += 1
    else:
        for c in ans:
            print c

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    ans = [0 for i in range(7)]
    for i in xrange(n):
        age = int(raw_input())
        if age <= 9:
            ans[0] += 1
        elif age <= 19:
            ans[1] += 1
        elif age <= 29:
            ans[2] += 1
        elif age <= 39:
            ans[3] += 1
        elif age <= 49:
            ans[4] += 1
        elif age <= 59:
            ans[5] += 1
        else:
            ans[6] += 1
    for c in ans:
        print c
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

import networkx as nx

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

g = nx.Graph()
for i in range(n - 1):
    g.add_edge(*map(lambda x: int(x) - 1, input().split()))

a = [0] * n
b = [True] * n
for i in range(q):
    p, x = map(int, input().split())
    a[p - 1] += x

d = deque([0])
b[0] = False

while len(d):
    p = d.popleft()
    for i in g.neighbors(p):
        if b[i]:
            a[i] += a[p]
            b[i] = False
            d.append(i)
print(*a)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque

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

graph = [deque([]) for _ in range(n + 1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

a = [0] * -~n
b = [True] * -~n
for i in range(q):
    p, x = map(int, input().split())
    a[p] += x

d = deque([1])
b[1] = False

while len(d):
    p = d.popleft()
    for i in graph[p]:
        if b[i]:
            a[i] += a[p]
            b[i] = False
            d.append(i)
print(*a[1:])
### BUGGY CODE ###

N ,M = map(int, input().split())
A_list = [int(i) * (-1) for i in input().split()]


import heapq
for i in range(M):
    heapq.heapify(A_list)
    x = heapq.heappop(A_list) / 2
    heapq.heappush(A_list, (-1)*int(-x))

print(-sum(A_list))


### FIXED CODE ###

N ,M = map(int, input().split())
A_list = [int(i) * (-1) for i in input().split()]


import heapq

heapq.heapify(A_list)
for i in range(M):
    x = heapq.heappop(A_list)
    heapq.heappush(A_list, (-1)*(-x//2))

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

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
for i in range(n):
  tmp = a[:i]+a[i+1:]
  print(max(tmp))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
max_a = max(a)
if a.count(max(a)) == 1:
  sec_max = sorted(a)[-2]
else:
  sec_max = max_a

for i in range(n):
  if a[i] == max_a:
    print(sec_max)
  else:
    print(max_a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

import sys
input = sys.stdin.readline

INF = float("INF")

N, M, L = map(int, input().split())

cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0

for _ in range(M):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1-1, v2-1
    cost[v1][v2] = w
    cost[v2][v1] = w

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(
                cost[i][j],
                cost[i][k] + cost[k][j])

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            continue
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(
                cost[i][j],
                cost[i][k] + cost[k][j])

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = cost[s-1][t-1]
    if ans == INF:
        print(-1)
    else:
        print(ans - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
mn=min(h)
cnt=0
if(mn!=1):
    print("-1")
    exit()
r=len(h)
i=-1
while(True):
    i=i+1
    if i==r:
        break
    if(h[i]!=i+1):
        cnt=cnt+1
        del h[i]
        r=r-1
        i=i-1
print(cnt)


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
mn=min(h)
cnt=0
if(mn!=1):
    print("-1")
    exit()
i=1
for k in h:
    if(k==i):
        i=i+1
    else:
        cnt=cnt+1
print(cnt)
### BUGGY CODE ###

X = int(input())
ans = 0

for i in range(1, 1001):
  for j in range(2, 1001):
    num = i ** j
    if num < X:
      break
    ans = num

print(ans)

### FIXED CODE ###

X = int(input())
ans = 1

for i in range(1, X+1):
  for j in range(2, X+1):
    num = i ** j
    if num > X:
      break
    if num >= ans: 
      ans = num

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

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

light=1
ans=0
while True:
    if light==2:
        break
    elif light==buttun[light]:
        ans=-1
        break
    else:
        light=buttun[light]
        ans+=1
    if light==1:
        ans=-1
        break
print(ans)

### FIXED CODE ###

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

light=1
ans=0
while True:
    if light==2:
        break
    elif light==buttun[light]:
        ans=-1
        break
    else:
        tmp=light
        light=buttun[light]
        ans+=1
        buttun[tmp]=1
    if light==1:
        ans=-1
        break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

dfs(0,-1)
print(*lis)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

dfs(0,-1)
print(*lis)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
  ans *= A[i]
if ans == 0:
  print(0)
  exit()
elif ans > 10**18:
  print(-1)
  exit()
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
  print(0)
  exit()
for i in range(N):
  ans *= A[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

n = int(input())
S = []
for i in range(n):
  S.append(input())
T = list(set(S))
count = []
counter =  []
for i in range(len(T)):
  count.append(S.count(T[i]))
  counter.append(T[i])
best = max(count)
ans = []
for i in range(len(T)):
  if count[i] == best:
    ans.append(counter[i])
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i]) 

### FIXED CODE ###

from collections import Counter
n = int(input())
S = []
for i in range(n):
  S.append(input())
S = sorted(S)
c = Counter(S)
X = c.most_common()
A = []
for i in range(len(X)):
  if X[0][1] == X[i][1]:
    A.append(X[i][0])
  else:
    break
A = sorted(A)
for i in range(len(A)):
  print(A[i])
### BUGGY CODE ###

n = int(input())
hs = input().split()

h = []
for s in hs:
    h.append(int(s))

b = True
for i in range(0,n):
    for j in range(i,n):
        if h[i] - h[j] > 1:
            print("No")
            b = False
if b:
    print("Yes")


### FIXED CODE ###

n = int(input())
hs = input().split()

h = []
for s in hs:
    h.append(int(s))

max = 0
for i in range(0,n):
    if max < h[i]:
        max = h[i]
    if max - h[i] > 1:
        print("No")
        exit()

print("Yes")
### BUGGY CODE ###

def main():
    from collections import deque
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    q = deque()
    if s[0][0] == '#':
        q.append((0, 0, 1))
    else:
        q.append((0, 0, 0))

    while q:
        r, c, cnt = q.popleft()
        if r == H - 1 and c == W - 1:
            print(cnt)
            return
        if r < H - 1:
            if s[r + 1][c] == '#':
                q.append((r + 1, c, cnt + 1))
            else:
                q.appendleft((r + 1, c, cnt))
        if c < W - 1:
            if s[r][c + 1] == '#':
                q.append((r, c + 1, cnt + 1))
            else:
                q.appendleft((r, c + 1, cnt))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    cost = [[H * W] * W for _ in range(H)]
    cost[0][0] = x

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

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

b=[]
for i in range(n):
    if i%2==0:
        b.append(a[i])
    else:
        b.insert(0, a[i])
if n%2!=0:
    b.reverse()
print(' '.join(map(str,b)))


### FIXED CODE ###

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

odd = []
even = []
for i in range(n):
    if i%2==0:
        even.append(a[i])
    else:
        odd.append(a[i])
if n%2!=0:
    b=even[::-1]+odd
else:
    b=odd[::-1]+even

print(' '.join(map(str,b)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = list(map(int, input().split()))
B.sort()
C = list(map(int, input().split()))
C.sort()
count = [0]*N
answer = 0
z = 0

for i in range(N):
    if B[0] >= C[N-i-1]:
        break
    z += 1
count[0] = z
for i in range(1, N):
    x = z
    for j in range(z):
        if B[i] < C[N-z+j]:
            break
        else:
            x -= 1
    count[i] = x
y = 0
for i in range(N):
    if A[0] >= B[N-i-1]:
        break
    answer += count[N-i-1]
    y += 1

for i in range(1, N):

    for j in range(y):
        if A[i] >= B[N-j-1]:
            break
        answer += count[N-j-1]
#print(count)
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)
count = [0]*N
answer = 0
z = 0
for i in range(N):
    if B[N-1] >= C[i]:
        break
    z += 1
count[N-1] = z
for i in range(1, N):
    k=z
    for j in range(k):
        if B[N-1-i] < C[k-1-j]:
            break
        else:
            z -= 1      
    count[N-1-i] = z
sum_matrix = [0]*(N+1)
y = 0
for i in range(N):
    sum_matrix[i+1] = sum_matrix[i] + count[i]
for i in range(N):
    if A[N-1] >= B[i]:
        break
    answer += count[i]
    y += 1
for i in range(1, N):
    x = y
    for j in range(x):
        if A[N-1-i] < B[x-1-j]:
            break        
        y -= 1
    answer += sum_matrix[y]
print(answer)
### BUGGY CODE ###

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

Asum=[0]
Bsum=[0]

for i in range(N):
    Asum.append(Asum[-1]+A[i])
    if Asum[i]>K:
        break
        
for i in range(M):
    Bsum.append(Bsum[-1]+B[i])
    if Bsum[i]>K:
        break
    
m=0
for i in range(len(Asum)):
    for j in range(len(Bsum)):
        if Asum[i]+Bsum[j]<=K and m<i+j:
            m=i+j
print(m)
        

### FIXED CODE ###

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

Asum=[0]
Bsum=[0]

for i in range(N):
    Asum.append(Asum[-1]+A[i])
        
for i in range(M):
    Bsum.append(Bsum[-1]+B[i])
    
m=0
j=M

for i in range(len(Asum)):
    if Asum[i]>K:
        break
    while Asum[i]+Bsum[j]>K:
        j-=1
    if m<i+j:
        m=i+j
        
print(m)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp = [[[-10**9,-10**9] for _ in range(n//2+2)] for _ in range(n+1)]
	dp[1][1][1]=a[1]
	for i in range(0,2):
		dp[i][0]=[0,0]
	for i in range(1,n+1):
		if i-1 >= 3:
			dp[i][(i-1)//2][0]=max(dp[i-1][(i-1)//2][0], dp[i-1][(i-1)//2][1])
			dp[i][(i-1)//2][1]=max(dp[i-1][(i-1)//2-1][0]+a[i], dp[i-2][(i-1)//2-1][0]+a[i])
		if i >= 2:
			dp[i][i//2][0]=max(dp[i-1][i//2][0], dp[i-1][i//2][1])
			dp[i][i//2][1]=max(dp[i-1][i//2-1][0]+a[i], dp[i-2][i//2-1][0]+a[i])
		if i >= 2:
			dp[i][(i+1)//2][1]=max(dp[i-1][(i+1)//2-1][0]+a[i], dp[i-2][(i+1)//2-1][0]+a[i])
	print(max(dp[n][n//2]))
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp_t = defaultdict(lambda: -10**18)
	dp_f =  defaultdict(lambda: -10**18)
	dp_f[(0,0)]=0
	for i in range(1,n+1):
		dp_f[(i,(i-1)//2)]=max(dp_f[(i-1,(i-1)//2)], dp_t[(i-1,(i-1)//2)])
		dp_t[(i,(i-1)//2)]=dp_f[(i-1,(i-1)//2-1)]+a[i]
		dp_f[(i,(i-1)//2+1)]=max(dp_f[(i-1,(i-1)//2+1)], dp_t[(i-1,(i-1)//2+1)])
		dp_t[(i,(i-1)//2+1)]=dp_f[(i-1,(i-1)//2)]+a[i]
	print(max(dp_t[(n,n//2)],dp_f[(n,n//2)]))
if __name__ == '__main__':
	main()
### 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*10), an ,0 )

print(ans%prime)

### 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 ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

# 無限大の値
f_inf = float('inf')

# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)

# 初期条件
dp[0] = 0

# 足場 i-1 から足場 i へと移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
# 足場 i-j から足場 i へと移動する。コストは |h[i]−h[i-j]|
for i in range(1, n):
    for j in range(1, k+1):
        # i-kが負の場合は、スタートはh[0]になる。
        if i-k<0:
            dp[i] = abs(h[i]-h[0])
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[n-1])



### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = np.zeros(n, dtype=int)
h = np.array(h)


for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])