Harryxun/stf_run huggingface dataset:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    import numpy as np
    import scipy.sparse.csgraph as sp
    inf = float('inf')
    d = np.full((n, n), inf)
    for i in range(n):
        d[i][i] = 0
    for a, b in ab:
        d[a-1][b-1] = 1
        d[b-1][a-1] = 1
    # indices=xでxからの単一始点に,return_predecessors=Trueで経路が出る
    s = sp.shortest_path(d, indices=0)
    print("Yes")
    for i in range(1, n):
        minimum = 10**9
        dire = None
        for j in g[i]:
            if s[j] < minimum:
                minimum = s[j]
                dire = j
        print(dire+1)


main()


### FIXED CODE ###

def main():

    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    import heapq
    h = [(0, 0)]
    heapq.heapify(h)
    d = [10**10]*n
    while h:
        dis, i = heapq.heappop(h)
        if d[i] == 10**10:
            d[i] = dis
            for j in g[i]:
                if d[j] == 10**10:
                    heapq.heappush(h, (dis+1, j))

    print("Yes")
    for i in range(1, n):
        minimum = 10**9
        dire = None
        for j in g[i]:
            if d[j] < minimum:
                minimum = d[j]
                dire = j
        print(dire+1)


main()
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1
idx = 0
crash = A[idx]
for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        if idx < M:
            crash = A[idx]
        continue
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])


### FIXED CODE ###

N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
crash = 0
idx = 0
for i in range(M):
    A.append(int(input()))
    if i == 0:
        crash = A[0]
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        if idx < M:
            crash = A[idx]
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
max_n=sum_n
for i in range(len(ans)-end+1):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         break
      now=0
   max_n=max(sum_n,max_n)
print(max_n)

### FIXED CODE ###

N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
   plus=0
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
   plus=1
max_n=sum_n
for i in range(len(ans)-end+plus):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         print(max_n)
         exit()
      now=0
   max_n=max(sum_n,max_n)
print(max_n)
s = input()

if s[0] == s[1] or s[1] == s[2] or s[2] == pas[3]:
    print('Bad')
else:
    print('Good')




### FIXED CODE ###

s = input()

if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    print('Bad')
else:
    print('Good')
import math
from functools import reduce
def gcbd_list(numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = list(map(int, input().split()))
P = [False] * (16 + 1)
c = True
for i in range(N):
    if P[A[i]] == True:
        c = False
    P[A[i]] = True
    for j in range(2, math.floor(A[i]**0.5)+1):
        if A[i] % j == 0:
            if P[j] == True:
                c = False
            P[j] = True
if c == True:
    print('pairwise coprime')
    exit()
if gcbd_list(A) == 1:
    print('setwise coprime')
    exit()
print('not coprime')


### FIXED CODE ###

import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = list(map(int, input().split()))
M = [0] * (10**6+1)
for i in A:
    M[i] += 1
if gcd_list(A) > 1:
    print('not coprime')
    exit()
for i in range(2,10**6+1):
    c = 0
    for j in range(i,10**6+1,i):
        c += M[j]
    if c > 1:
        print('setwise coprime')
        exit()
print('pairwise coprime')
N = int(input())
H = list(map(int, input().split()))

ans = 1
for i in range(1, N-1, 1):
    #print((H[i] - H[i+1]))
    #print(i)
    if ((H[i-1] - H[i]) >= 1) & ((H[i] - H[i+1]) >= 1):
        print('No')
        ans = -1
        break
    elif ((H[i-1] - H[i]) == 0) & ((H[i] - H[i+1]) == 1):
        print('No')
        ans = -1
        break
    elif ((H[i-1] - H[i]) >= 2):
        print('No')
        ans = -1
        break
    elif ((H[i] - H[i+1]) >= 2):
        print('No')
        ans = -1
        break
    else:
        continue

if (N == 2) & (H[0] - H[1] >= 2):
    print('No')
    ans = -1

if (ans == 1): print('Yes')

### FIXED CODE ###

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

ans = 1
for i in reversed(range(1, N, 1)):
    if (H[i-1] - H[i]) == 1:
        H[i-1] -= 1
    if (H[i-1] - H[i]) > 1:
        print('No')
        ans = -1
        break
if ans == 1: print('Yes')
import sys
import math
input = lambda: sys.stdin.readline().rstrip()


def count_div(N, C, D):

    t = N // C + N // D - N // (C * D // math.gcd(C, D))
    return N - t


def solve():

    A, B, C, D = map(int, input().split())
    ans = count_div(B, C, D) - count_div(A - 1, C, D)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import fractions
input = lambda: sys.stdin.readline().rstrip()


def count_div(N, C, D):

    t = N // C + N // D - N // (C * D // fractions.gcd(C, D))
    return N - t


def solve():

    A, B, C, D = map(int, input().split())
    ans = count_div(B, C, D) - count_div(A - 1, C, D)
    print(ans)


if __name__ == '__main__':
    solve()
# 標準入力
X, Y, A, B, C = map(int, input().split())
red = list(map(int,input().split()))
green = list(map(int,input().split()))
trans = list(map(int,input().split()))
red.sort(reverse=True)
green.sort(reverse=True)
trans.sort(reverse=True)
apple = red[:X] + green[:Y]
j = 0
for i in range(X + Y):
    if apple[i] < trans[j]:
        apple[i] = trans[j]
        j = j + 1
    else:
        continue
print(sum(apple))    
            

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
red = list(map(int,input().split()))
green = list(map(int,input().split()))
trans = list(map(int,input().split()))

red.sort(reverse=True)
green.sort(reverse=True)
trans.sort(reverse=True)
apple = red[:X] + green[:Y]
apple.sort()

j = 0
for i in range(X + Y):
    if apple[i] < trans[j]:
        apple[i] = trans[j]
        j = j + 1
        if j == C:
            break
    else:
        continue
print(sum(apple))
S = list(input())
S_len = len(S)

def dfs(S):
    slen = len(S)
    for i in range(slen -1 ):
        if S[i] != S[i+1]:
            del S[i:i+2]
            dfs(S)
            break;
    End_len = len(S)
    ans = S_len - End_len
    return ans

if __name__ == '__main__':
    print(dfs(S))

### FIXED CODE ###

s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))
abc = input().split()
a =int(a)
b = int(b)
c = int(c)
if a<b and b<c:
    print("Yes")
else:
    print("No")
    


### FIXED CODE ###

a,b,c = input().split()
a =int(a)
b = int(b)
c = int(c)
if a<b and b<c:
    print("Yes")
else:
    print("No")
from numpy import array
from numpy.linalg import solve
import sys

N=input()
A=map(int, sys.stdin.readline().split())

L=[]
for i in range(N-1):
	L.append ([0]*i+[1,1]+[0]*(N-i-2)) 

L.append([1]+[0]*(N-2)+[1])


a=array(L) 
b=array(A)       
L=solve(a,b) 

for ans in L:
	print int(ans)*2,


### FIXED CODE ###

import sys
from collections import deque

N=input()
A=map(int, sys.stdin.readline().split())
A=map(lambda x: x*2, A)

a=sum(A)/2

for i in range(1,N):
	if i%2==1:
		a-=A[i]

#a
print a,

prev=a
for x in A[:-1]:
	x-=prev
	print x,
	prev=x
N, K = map(int, input().split()) # 横に2個
S = [int(i) for i in list(input())]

N0 = []
N1 = []
n0 = 0
n1 = 0
for s in S:
    if s == 0:
        if n1 > 0:
            N1.append(n1)
            n1 = 0
        n0 += 1
    if s == 1:
        if n0 > 0:
            N0.append(n0)
            n0 = 0
        n1 += 1
if n0 > 0:
    N0.append(n0)
if n1 > 0:
    N1.append(n1)

M0 = [0]
m0 = 0
for n0 in N0:
    m0 += n0
    M0.append(m0)

M1 = [0]
m1 = 0
for n1 in N1:
    m1 += n1
    M1.append(m1)
#print(M0)
#print(M1)

c = 0 if S[0] == 0 else 1

if len(N1) == 1 and len(N0) == 0:
    ans = N1[0]
elif len(N1) == 0 and len(N0) == 1:
    ans = N0[0]
else:
    ans = 0
    for i in range(N):
        if i + K >= len(M0):
            break
        if c == 0:
            if i == 0:
                l = M0[K] + M1[i+K]
            elif i == len(M1)-1:
                l = M0[i+K]-M0[i] + M1[i+K-1]-M1[i-1]
            else:
                l = M0[i+K]-M0[i] + M1[i+K]-M1[i-1]
        else:
            if i == len(M1)-2:
                l = M0[i+K]-M0[i] + M1[i+K]-M1[i]
            else:
                l = M0[i+K]-M0[i] + M1[i+K+1]-M1[i]
        #print(i, l)
        ans = max(ans, l)
print(ans)

### FIXED CODE ###

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

l = 0
r = 0
change = 0 if S[0] == '1' else 1
ans = 0
while l < N and r < N:
    #print(l, r, change)
    ans = max(ans, r-l+1)
    if r == N-1:
        break
    if S[r] == '0':
        r += 1
    else:
        if S[r+1] == '0':
            if change < K:
                change += 1
                r += 1
            else:
                if S[l] == '0' and S[l+1] == '1':
                    r += 1
                l += 1
        else:
            r += 1
print(ans)
5
2 5 2
2 3 10
1 3 8
3 4 2

### FIXED CODE ###

n = int(input())

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

color = [-1] * n
dist = [0] * n

import queue
def dfs(v):
    color[v] = dist[v] % 2
    q = queue.LifoQueue()
    q.put(v)

    while not q.empty():
        vv = q.get()
        for next_v in g[vv]:
            if color[next_v[0]] == -1 and next_v[1] != 0:
                dist[next_v[0]] = dist[vv] + next_v[1]
                color[next_v[0]] = dist[next_v[0]] % 2
                q.put(next_v[0])

# 0を始点として各点までの距離を求める
dfs(0)

for c in color:
    print(c)
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()

ave = B[N//2]
ans = 0
for i in range(N):
    ans1 += abs(B[i]-ave)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(min(ans1,ans2))
A, B, C, X, Y = map(int, input().split())
price = [0]*(max(X, Y)+1)
prine[0] = A*X+B*Y
for i in range(1, max(X, Y)+1):
  price [i] = 2*C*i+A*max(0, X-i)+B*max(0,Y-i)
print(min(price))

### FIXED CODE ###

A, B, C, X, Y = map(int, input().split())
price = [0]*(max(X, Y)+1)
price[0] = A*X+B*Y
for i in range(1, max(X, Y)+1):
  price [i] = 2*C*i+A*max(0, X-i)+B*max(0,Y-i)
print(min(price))
if x=0:
  return 1
else:
  return 0

### FIXED CODE ###

x=int(input())

if x==0:
  print(1)
elif x==1:
  print(0)
n = int(input())
print((n-n//2)/n))

### FIXED CODE ###

n = int(input())
print((n-n//2)/n)
hoge = input().split
while i < range(len(hoge)):
  if i%2==0 and hoge[i] == 'L' or 'D' or 'U':
    pass
  elif i%2==1 and hoge[i] == 'R' or 'D' or 'U':
    pass
  else:
    break
  i+=1
if i == len(hoge):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import re
hoge = list(input())
i = 0
while i < len(hoge):
    if i%2==0 and re.findall(r'[RDU]',hoge[i]):
        pass
    elif i%2==1 and re.findall(r'[LDU]',hoge[i]):
        pass
    else:
        break
    i+=1
if i == len(hoge):
  print('Yes')
else:
  print('No')
n,k = map(int,input().split())
m = n//k
a = n - (k*m)
    
print(min(a,abs(a-k)))

### FIXED CODE ###

x,y,z = map(int,input().split())

print(z,x,y)
num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = "0"
while remain_match > 0:
    for Ai in A:
        if dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans[1:]))


### FIXED CODE ###

num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = "0"
while remain_match > 0:
    for Ai in A:
        if remain_match >= num_A[Ai] and dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans[1:]))
import math
N = int(input())
num = 1
ans = 0
for i in range(1, N + 1):
    num *= i

maxx = int(math.sqrt(num)) + 2

for i in range(1, (num // 2) + 3):
    if num % i == 0:
        ans += 1
        ans %= (10**9) + 7

print(ans + 1)

### FIXED CODE ###

import math
import collections

N = int(input())
a = math.factorial(N)
check = []
ans = 1
i = 2

while a != 1:
    if a % i == 0:
        a //= i
        check.append(i)
    else:
        i += 1
        
check = collections.Counter(check).values()
for i in check:
    ans *= (i+1)
    ans %= 10**9+7
print(ans)
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
A = list(map(int, input().split()))

dict_A = {i: 0 for i in range(1, n+1)}
for a in A:
    dict_A[a] += 1

num_list = [[] for _ in range(n)]
for key in dict_A.keys():
    num_list[dict_A[key]].append(key)

ans = 0
count = len(dict_A.keys())
pointer = 1
while count > k:
    if len(num_list[pointer]) == 0:
        pointer += 1
        continue
    ans += pointer
    count -= 1
    del num_list[pointer][0]
print(ans)


### FIXED CODE ###

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

n, k = map(int, input().split())
A = list(map(int, input().split()))

dict_A = {}
for a in A:
    if a not in dict_A:
        dict_A[a] = 1
    else:
        dict_A[a] += 1

if len(dict_A.keys()) <= k:
    print(0)
    exit()

sorted_A = sorted(dict_A.items(), key=lambda x: x[1])

ans = 0
for i in range(len(dict_A.keys())-k):
    ans += sorted_A[i][1]

print(ans)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,M=map(int,readline().split())
bomb=[[0 for j in range(2)] for i in range(M)]
h=[0]*M
w=[0]*M
for i in range(M):
    x,y=map(lambda x: int(x) - 1, readline().split())
    bomb[i]=x,y
    h[x]+=1
    w[y]+=1
maxh=max(h)
maxw=max(w)
R=[h for h, x in enumerate(h) if x == maxh] 
C = [w for w, y in enumerate(w) if y == maxw]
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxh + maxw)
            exit()
print(maxh + maxw - 1)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int, readline().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in readlines()]
X = [0] * H 
Y = [0] * W 
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  
C = [w for w, y in enumerate(Y) if y == maxY] 

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
A,B = map(int,input())
if A-(2*B) > 0:
  print(A-(2*B))
else:
  print(0)

### FIXED CODE ###

A,B = map(int,input().split())
if A-(2*B) > 0:
  print(A-(2*B))
else:
  print(0)
a, b, k =  map(int, input().split())

x = list(range(a, b+1))

i = x[:k]
j = x[-k:]

for k in i:
    print(k)

for k in j:
    print(k)


### FIXED CODE ###

a, b, k = map(int, input().split())

if (abs(a-b) + 1) / 2 <= k:
  for i in range(a, b+1):
    print(i)
  exit()

for i in range(k):
  print(a+i)

for i in sorted([b - i for i in range(k)]):
  print(i)
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    import numpy as numpy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n))
    s, p = shortest_path(a, return_predecessors=True, directed=False)
    l = [[True] * n for _ in range(n)]
    for start in range(n - 1):
        for goal in range(start + 1, n):
            path = get_path(start, goal, p)
            for i in range(len(path) - 1):
                l[path[i]][path[i + 1]] = False
                l[path[i + 1]][path[i]] = False
    ans = 0
    for i, j in zip(row, col):
        if l[i][j]:
            ans += 1
    print(ans)


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


resolve()


### FIXED CODE ###

def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    import numpy as numpy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    s, p = shortest_path(a, return_predecessors=True, directed=False)
    l = [[True] * n for _ in range(n)]
    for start in range(n - 1):
        for goal in range(start + 1, n):
            path = get_path(start, goal, p)
            for i in range(len(path) - 1):
                l[path[i]][path[i + 1]] = False
                l[path[i + 1]][path[i]] = False
    ans = 0
    for i, j in zip(row, col):
        if l[i][j]:
            ans += 1
    print(ans)


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


resolve()
alpha = 'abcdefghijklmnopqrstuvwxyz'
C = input().split()
print(alpha[alpha.index(C)+1])

### FIXED CODE ###

alpha = 'abcdefghijklmnopqrstuvwxyz'
C = input()
print(alpha[alpha.index(C)+1])
from sys import stdin
from functools import lru_cache


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


class Rec_memo:
    def __init__(self, N, h_arr):
        self.dp = [float('inf')] * (N+2)
        self.h_arr = h_arr

    def rec(self, i):
        if self.dp[i] != float('inf'):
            return self.dp[i]
        elif i == 0:
            return 0
        else:
            self.dp[i] = chmin(self.dp[i],self.rec(i-1)+abs(self.h_arr[i]-self.h_arr[i-1]))
            if i>1:
                self.dp[i] = chmin(self.dp[i],self.rec(i-2)+abs(self.h_arr[i]-self.h_arr[i-2]))
            return self.dp[i]


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    h_arr = [0] * (N+2)
    h_arr[0:N] = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    # dp[i]:=カエルが足場iへと移動するのに必要な最小コスト
    dp = [float('inf')] * (N+2)  # 最小化問題
    dp[0] = 0                    # 初期条件
    
    # 貰うDP
    #for i in range(0,N):
    #    dp[i] = chmin(dp[i],dp[i-1]+abs(h_arr[i]-h_arr[i-1]))
    #    if i > 1:
    #        dp[i] = chmin(dp[i],dp[i-2]+abs(h_arr[i]-h_arr[i-2]))
    #cnt = dp[N-1]

    # 配るDP
    #for i in range(0,N):
    #    dp[i+1] = chmin(dp[i+1],dp[i]+abs(h_arr[i]-h_arr[i+1]))
    #    dp[i+2] = chmin(dp[i+2],dp[i]+abs(h_arr[i]-h_arr[i+2]))
    #cnt = dp[N-1]

    # メモ化再帰
    memo = Rec_memo(N,h_arr)
    cnt = memo.rec(N-1)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    h_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [float('inf')] * N  # 最小化問題
    dp[0] = 0                # 初期条件
    
    for i in range(0,N):
        dp[i] = chmin(dp[i],dp[i-1]+abs(h_arr[i]-h_arr[i-1]))
        if i > 1:
            dp[i] = chmin(dp[i],dp[i-2]+abs(h_arr[i]-h_arr[i-2]))
    cnt = dp[N-1]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

div = max(int(Q**.5), 1)
B = N // div

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * N

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

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


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

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