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

import sys

file_input = sys.stdin

n = file_input.readline()

def distance(s_p1, s_p2):
    x1, y1 = map(float, s_p1.split())
    x2, y2 = map(float, s_p2.split())
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

import itertools

min_d = 400

for p1, p2 in itertools.combinations(file_input, 2):
    min_d = min(min_d, distance(p1, p2))

print('{:f}'.format(min_d))

### FIXED CODE ###

import itertools

def _get_distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

def _get_min_distance(points):
    min_d = 400
    for p1, p2 in itertools.combinations(points, 2):
        min_d = min(min_d, _get_distance(p1, p2))
    return min_d

def closest_pair_distance(points):
    n = len(points)
    if n <= 3:
        return _get_min_distance(points)
    else:
        mid = n // 2
        px, py = zip(*points)
        if len(set(px)) > len(set(py)):
            points.sort(key = lambda p: p[0])
            # axis: x; 0, y; 1
            axis1 = 0
            axis2 = 1
        else:
            points.sort(key = lambda p: p[1])
            axis1 = 1
            axis2 = 0
        A_points = points[:mid]
        B_points = points[mid:]
        d_Amin = closest_pair_distance(A_points.copy())
        d_Bmin = closest_pair_distance(B_points.copy())
        dist = min(d_Amin, d_Bmin)
        min_d = dist
        for ap in A_points[::-1]:
            if B_points[0][axis1] - ap[axis1] >= dist:
                break
            for bp in B_points:
                if bp[axis1] - ap[axis1] >= dist:
                    break
                if ap[axis2] - dist < bp[axis2] < ap[axis2] + dist:
                    min_d = min(min_d, _get_distance(ap, bp))
        return min_d

# Acceptance of input
import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [tuple(map(float, line.split())) for line in file_input]

# Solve
ans = closest_pair_distance(P)

print('{:f}'.format(ans))
### BUGGY CODE ###

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

#Union-Find

par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
root=set()

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            if b in root:
                root.remove(b)
            root.add(a)
            siz[a]+=siz[b]
        else:
            par[a]=b
            if a in root:
                root.remove(a)
            root.add(b)
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            
def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)
p=N*(N-1)//2
edge=[]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    edge.append([a,b])
ans=[p]
for i in reversed(range(1,M)):
    res=0
    union(edge[i][0],edge[i][1])
    for x in root:
        s=size(x)
        res+=s*(s-1)//2
    ans.append(max(p-res,0))
print(*ans[::-1],sep='\n')

### FIXED CODE ###

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

#Union-Find

par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
root=set()

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            if b in root:
                root.remove(b)
            root.add(a)
            siz[a]+=siz[b]
        else:
            par[a]=b
            if a in root:
                root.remove(a)
            root.add(b)
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)
    
edge=[]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    edge.append([a,b])
p=N*(N-1)//2
res=[p]
for i in reversed(range(1,M)):
    if(not same(edge[i][0],edge[i][1])):
        p=p-size(edge[i][0])*size(edge[i][1])
        union(edge[i][0],edge[i][1])
    res.append(p)
print(*res[::-1],sep='\n')
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = [(0, s, -1)]
  while len(que) > 0:
    (d, u, c) = heappop(que)
    if result[u, c] < d: continue
    for (t, c2) in edges[u]:
      cost = int(c != c2)
      if d + cost < result[t, c2]:
        result[t, c2] = d + cost
        heappush(que, (d + cost, t, c2))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)
### BUGGY CODE ###

from collections import Counter
n, p = map(int, input().split())
s = input()
s += '0'
p_cnt = 0
div_list = []

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        num = int(s[i:])
        div_list.append(num % p)

    div_ol = Counter(div_list)
    for v in div_ol.values():
        p_cnt += v * (v - 1) / 2



print(int(p_cnt))

### FIXED CODE ###

n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
        
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)
### BUGGY CODE ###

cnt = 0
R, G, B, N = map(int, input().split())

for r in range((N//R)+1):
    for g in range((N-r*R)//G+1):
        m = N - r*R - g*G
        if m == 0 or (m % B == 0 and m >= B):
            cnt += 1

print(cnt)

### FIXED CODE ###

cnt = 0
R, G, B, N = map(int, input().split())
comb = []
tmp = []
rgb = [R, G, B]

for r in range((N//R)+2):
    for g in range((N//G)+2):
        m = N - r*R - g*G
        if m == 0 or (m % B == 0 and m >= B):
            cnt += 1

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

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = tuple(map(int, input().split()))


def can_eat(t):
    F_time = sorted([t // f for f in F])
    training = 0
    for i in range(N):
        training += max(0, A[i] - F_time[i])
    return training <= K


# bisect
l, r = -1, 10 ** 12
while r - l > 1:
    m = (r + l) // 2
    if can_eat(m):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = tuple(map(int, input().split()))


def can_eat(t):
    F_time = sorted([t // f for f in F])
    training = 0
    for i in range(N):
        training += max(0, A[i] - F_time[i])
    return training <= K


# bisect
l, r = -1, 10 ** 12
while r - l > 1:
    m = (r + l) // 2
    if can_eat(m):
        r = m
    else:
        l = m
print(r)
### BUGGY CODE ###

N,A,B,C,D=map(int,input().split())
mod=10**9+7

F=[1]*(N+1)
for i in range(1,N+1):
  F[i]=F[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

invF=[1]*(N+1)
invF[N]=power(F[N],mod-2)
for i in range(0,N)[::-1]:
  invF[i]=(invF[i+1]*(i+1))%mod
  
dp=[[0]*(N+1) for i in range(B-A+2)]
dp[0][0]=1
for i in range(A,B+1):
  for j in range(N+1):
    dp[i-A+1][j]=(dp[i-A][j]+sum([dp[i-A][j-k*i]*F[N-j+k*i]*invF[N-j]*power(invF[i],k)*invF[k] for k in range(C,min(D,j//i)+1)]))%mod
    
print((dp[B-A+1][N])%mod)


        
  


    
                                      

### FIXED CODE ###

N,A,B,C,D=map(int,input().split())
mod=10**9+7

F=[1]*(N+1)
for i in range(1,N+1):
  F[i]=F[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

invF=[1]*(N+1)
invF[N]=power(F[N],mod-2)
for i in range(0,N)[::-1]:
  invF[i]=(invF[i+1]*(i+1))%mod
invp=[[0]*(N+1) for i in range(N+1)]
for i in range(N+1):  
  for k in range(N+1):
    if k==0:
      invp[i][k]=1
    else:
      invp[i][k]=(invp[i][k-1]*invF[i])%mod
dp=[[0]*(N+1) for i in range(B-A+2)]
dp[0][0]=1
for i in range(A,B+1):
  for j in range(N+1):
    dp[i-A+1][j]=dp[i-A][j]
    for k in range(C,min(D,j//i)+1):
      dp[i-A+1][j]+=(dp[i-A][j-k*i]*F[N-j+k*i]*invF[N-j]*invp[i][k]*invF[k])%mod
      dp[i-A+1][j]%=mod
    
print((dp[B-A+1][N])%mod)
### BUGGY CODE ###

def main():
    n,w=map(int,input().split())
    items=[]
    dp=[0 for i in range(w+1)]
    for i in range(n):
        wi,vi=map(int,input().split())
        for j in range(w-wi,-1,-1):
            dp[j+wi]=max(dp[j+wi],dp[j]+vi)
    print(max(dp))
if __name__=='__main__':
    main()


### FIXED CODE ###

n,w=map(int,input().split())
items=[]
dp=[0 for i in range(w+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(max(dp))
### BUGGY CODE ###

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

    dp = [10 ** 10] * n
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(2,n):
      ls = []
      for j in range(1,k+1):
      	ls.append(dp[i - j] + abs(h[i] - h[i - j]))
      dp[i] = min(ls)
    print(dp[n-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy
[n,k] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
dp = [0]
i_ls = []
now = 0
#dpのi番目の要素がi+1番目の足場までの最小コスト
for i in range(1,n):
    #i番目の足場
    if i < k:
        for j in range(i):
            i_ls.append(abs(a[i]-a[j])+dp[j])
        #print("i<k")
    else:
        for j in range(i-k,i):
            i_ls.append(abs(a[i]-a[j])+dp[j])
        #print("i>=k")
    dp.append(min(i_ls))
    #print(i_ls)
    i_ls = []

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

w=list(input())
now=0
num=len(w)
w.append(" ")
count=0
while now<num:
  if w[now]!="A":
    now+=1
  else:
    if w[now+1]!="B":
      now+=1
    else:
      if w[now+2]!="C":
        now+=1
      else:
        w[now]="B"
        w[now+1]="C"
        w[now+2]="A"
        count+=1
        back=now-1
        b=True
        while back>0 and b==True:
          if w[back]!="A":
            b=False
          else:
            w[back]="B"
            w[back+1]="C"
            w[back+2]="A"
            count+=1
            back-=1
        now+=1
print(count)


### FIXED CODE ###

w=input()
count=0
num=len(w)
w1=""
w+=" "
while count<num:
  if w[count]=="A":
    w1+="A"
    count+=1
  elif w[count]=="B":
    if w[count+1]=="C":
      w1+="D"
      count+=2
    else:
      w1+="B"
      count+=1
  else:
    w1+="C"
    count+=1
counta=0
ans=0
num=len(w1)
for i in range(num):
  if w1[i]=="A":
    counta+=1
  elif w1[i]=="D":
    ans+=counta
  else:
    counta=0
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
dp=[[[False for i in range(80*80)] for j in range(w)] for k in range(h)]
dp[0][0][d[0][0]] = True
for i in range(h):
    for j in range(w):
        for dis in range(80*80):
            if dp[i][j][dis]:
                if i+1<h:
                    dp[i+1][j][abs(dis-d[i+1][j])]=True
                    if dis+d[i+1][j]<80*80:
                        dp[i+1][j][dis+d[i+1][j]]=True
                if j+1<w:
                    dp[i][j+1][abs(dis-d[i][j+1])]=True
                    if dis+d[i][j+1]<80*80:
                        dp[i][j+1][dis+d[i][j+1]]=True
for dis in range(80*80):
    if dp[-1][-1][dis]:
        print(dis)
        break

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
maxd=1
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
        maxd=max(maxd,d[i][j])
dp=[[0 for j in range(w)] for k in range(h)]
c=20000
dp[0][0] |= 1 << c+d[0][0]
for i in range(h):
    for j in range(w):
        if i+1<h:
            dp[i+1][j] |= dp[i][j] << d[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d[i+1][j]
        if j+1<w:
            dp[i][j+1] |= dp[i][j] << d[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d[i][j+1]
m=1000000
cnt = 0
for x in bin(dp[h-1][w-1])[2:][::-1]:
    if x=='1':
        m=min(m,abs(cnt-c))
    cnt+=1
print(m)
### BUGGY CODE ###

def solve():
	N, *A = map(int, open(0).read().split())
	
	top = [A[0]]
	for i in range(1, N):
		da_min = 10**9
		color = -1
		for j in range(len(top)):
			da = A[i] - top[j]
			if da > 0:
				if da_min > da:
					da_min = da
					color = j
		if color != -1:
			top[color] = A[i]
		else:
			top.append(A[i])
	
	print(len(top))


if __name__ == '__main__':
	solve()

### FIXED CODE ###

from bisect import bisect_left
from collections import deque


def solve():
	N, *A = map(int, open(0).read().split())

	top = deque([A[0]])
	for a in A[1:]:
		if top[0] >= a:
			top.appendleft(a)
		else:
			index = bisect_left(top, a)
			top[index-1] = a
	
	print(len(top))


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

mod = 1000000007

pow3 = [1] * 100001
for i in range(1, 100001):
    pow3[i] = pow3[i - 1] * 3

s = input()

all_a = 0
all_c = 0
all_q = 0
for c in s:
    if c == 'A':
        all_a += 1
    elif c == 'C':
        all_c += 1
    elif c == '?':
        all_q += 1
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * pow3[all_q] % mod
        n += sum_a * (all_q - sum_q) * pow3[all_q - 1] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_q * (all_q - sum_q) * pow3[all_q - 2] % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_a * (all_q - sum_q - 1) * pow3[all_q - 2] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 2] % mod
        n += sum_q * (all_q - sum_q - 1) * pow3[all_q - 3] % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))


### FIXED CODE ###

mod = 1000000007

pow3 = [1] * 100001
for i in range(1, 100001):
    pow3[i] = pow3[i - 1] * 3 % mod

s = input()

all_a = 0
all_c = 0
all_q = 0
for c in s:
    if c == 'A':
        all_a += 1
    elif c == 'C':
        all_c += 1
    elif c == '?':
        all_q += 1
sum_a = 0
sum_c = 0
sum_q = 0
ans = 0

for c in s:
    n = 0
    if c == 'B':
        n += sum_a * (all_c - sum_c) * pow3[all_q] % mod
        n += sum_a * (all_q - sum_q) * pow3[all_q - 1] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_q * (all_q - sum_q) * pow3[all_q - 2] % mod
    elif c == '?':
        n += sum_a * (all_c - sum_c) * pow3[all_q - 1] % mod
        n += sum_a * (all_q - sum_q - 1) * pow3[all_q - 2] % mod
        n += sum_q * (all_c - sum_c) * pow3[all_q - 2] % mod
        n += sum_q * (all_q - sum_q - 1) * pow3[all_q - 3] % mod
    ans += n % mod
    if c == 'A':
        sum_a += 1
    elif c == 'C':
        sum_c += 1
    elif c == '?':
        sum_q += 1
print(int(ans % mod))
### BUGGY CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
for i in start:
    if i in goal:
        ans = 'POSSIBLE'
        break
print(ans)


### FIXED CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)
### BUGGY CODE ###

N,M,K = map(int,input().split())
MOD = 998244353

def nCr(n,r):
  ansMul, ansDiv = 1, 1
  for i in range(r):
    ansMul *= (n-i)
    ansDiv *= (i+1)
    ansMul %= MOD
    ansDiv %= MOD
  return (ansMul * pow(ansDiv, MOD-2, MOD)) % MOD

res = 0
for x in range(K, -1, -1):
  res += M*pow(M-1, N-x-1, MOD) * nCr(N-1, x)%MOD
  res %= MOD

print(res)

### FIXED CODE ###

N,M,K = map(int,input().split())
MOD = 998244353

class Combination:
  def __init__(self, n_max, mod=998244353):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

comb = Combination(2*10**5)

res = 0
for x in range(K+1):
  res += (M * pow(M-1, N-x-1, MOD)%MOD * comb(N-1, x)%MOD)%MOD
  res %= MOD

print(res % MOD)
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.sort()
can = []
p = 0
ans = 0
for i in range(M+1):
    while p<N and (AB[p][0] <= i) :
        index = bisect.bisect_left(can,AB[p][1])
        can.insert(index,AB[p][1])
        p += 1
        
    if can != []:
        ans += can.pop(-1)
print(ans)

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.sort()
can = []
p = 0
ans = 0
for i in range(M+1):
    while p<N and (AB[p][0] <= i) :
        heapq.heappush(can,-AB[p][1])
        p += 1
        
    if can != []:
        ans += heapq.heappop(can)
print(-ans)
### BUGGY CODE ###

import math

n = int(input())
n += 1
ans = 0
for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            ans += math.gcd(i, math.gcd(j, k))

print(ans)


### FIXED CODE ###

import math

n = int(input())
n += 1
ans = 0
for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            ans += math.gcd(i, math.gcd(j, k))

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

# B
N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [0]*N

cost[0] = 0
for i in range(1,N):
    cost_tmp = []
    for j in range(0,min(K,i)):
        cost_tmp.append(abs(h[i - (1+j)] - h[i]) + cost[i - (1+j)])
    cost[i] = min(cost_tmp)

print(cost[-1])

    

### FIXED CODE ###

# B(TLE) 2104ms

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
cost = np.zeros(N, dtype="int32")

cost[0] = 0
for i in range(1,N):
    start = 0 if i < K else i-K
    cost[i] = np.min(cost[start:i] + np.abs(h[i]-h[start:i]))

print(cost[-1])
### BUGGY CODE ###

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())
a = list(map(int, rl().split()))
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())
a = list(map(int, rl().split()))
if 0 in a:
    print(0)
else:
    ans = 1
    for i in a:
        ans *= i
        if ans > 10**18:
            print(-1)
            exit()
    else:
        print(ans)
### BUGGY CODE ###

import math

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

flag = 0 # 0をpairwise coprime

for i in range(N): 
    for j in range(i+1, N):
        if math.gcd(A[i], A[j]) != 1:
            flag = 1 #1はpairwise coprimeではない
            break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

### FIXED CODE ###

import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)
### BUGGY CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]
count = 0

for i in range(N):
    for k in range(i + 1, N):
        if s[i] == s[k]:
            count += 1
print(count)

### FIXED CODE ###

import collections

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

count = collections.Counter(s)
ans = 0

for i in count.values():
    ans += i * (i - 1) / 2

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

import heapq
import bisect
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

lists = [[] for _ in range(10**5 + 1)]
availables = []
for A, B in ABs:
    bisect.insort(lists[A], B)

ans = 0
for i in range(1, M + 1):
    availables = list(heapq.merge(availables, lists[i]))
    if availables:
        ans += availables.pop()

print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

heapq.heapify(ABs)
availables = []
ans = 0
for i in range(1, M + 1):
    while ABs:
        a = heapq.heappop(ABs)
        if a[0] == i:
            heapq.heappush(availables, -a[1])
        else:
            heapq.heappush(ABs, a)
            break
    if availables:
        ans -= heapq.heappop(availables)

print(ans)