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

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
for j in range(k):
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    FLAG = True
    for i in range(n):
        tmp += imos[i]
        if tmp != n - 1:
            FLAG = False
        a[i] = tmp
    if FLAG:
        break
print(*a)


### FIXED CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
changed=set(range(n))
for j in range(k):
    for i in changed:
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
    if j>50:
        break
print(*a)
### BUGGY CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
li=[]
idx_li=[1]
for i in range(k):
    idx=a[idx-1]
    if idx in idx_li:
        break
    idx_li.append(idx)
non_loop=idx_li[:idx_li.index(idx)]
loop = idx_li[idx_li.index(idx):]
size=len(loop)
print(loop[(k-len(non_loop))%size])
    

### FIXED CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
idx_li=[]
ord_=[-1]*n
flag=False
for i in range(k):
    idx_li.append(idx)
    ord_[idx-1]=1
    idx=a[idx-1]
    if ord_[idx-1]==1:
        flag=True
        break
if flag:
    #non_loop=idx_li[:idx_li.index(idx)]
    loop = idx_li[idx_li.index(idx):]
    
    size=len(loop)
    print(loop[(k-(len(idx_li)-len(loop)))%size])
else:
    print(idx)
### BUGGY CODE ###

N,W=map(int,input().split())
numbers=[]
for _ in range(N):
    w,v=input().split()
    numbers.append([int(w),int(v)])
def chmax(a,b):
    if a>=b:
        return a
    else:
        return b
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for a in range(N):
    for sum_w in range(W+1):
        if sum_w-numbers[a][0]>=0:
            dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w-numbers[a][0]]+numbers[a][1])
        dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w])
print(dp[N][W])


### FIXED CODE ###

N,W=map(int,input().split())
numbers=[]
for _ in range(N):
    w,v=input().split()
    numbers.append([int(w),int(v)])
def chmax(a,b):
    if a>=b:
        return a
    else:
        return b
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for a in range(N):
    for sum_w in range(W+1):
        if sum_w-numbers[a][0]>=0:
            dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w-numbers[a][0]]+numbers[a][1])
        dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w])
print(dp[N][W])
### BUGGY CODE ###

def main():
  from fractions import Fraction
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = {}
  dd_flag = {}
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      ba = Fraction(-b, a)
      ab = Fraction(a, b)
      if ba in dd_ba:
        dd_ba[ba] += 1
      else:
        dd_ba[ba] = 1
      
      if not(ab in dd_ba):
        dd_ba[ab] = 0
        
      dd_flag[ba] = False
      dd_flag[ab] = False

  ans = (2**zero_one_count + 2**one_zero_count -1)

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

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

n,q = map(int,input().split())
s = input()
questions = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  l,r = questions[i]
  print(s[l - 1:r].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
questions = [tuple(map(int,input().split())) for _ in range(q)]
A_Flag = False
t = [0]*(n + 1)
for i in range(0,n):
  if s[i:i+2] == "AC":
    t[i + 1] = t[i] + 1
  else:
    t[i + 1] = t[i]
for i in range(q):
  l,r = questions[i]
  print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r)for a,b in zip(r+[0]*n,[0]*~-n+r)))

### FIXED CODE ###

n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))
### BUGGY CODE ###

N=int(input())
ls=[]
for i in range(N):
  ls.append(int(input()))
for i in range(N):
  x=ls[0]
  ls.pop(0)
  print(max(ls))
  ls.append(x)

### FIXED CODE ###

N=int(input())
maxi=0
smaxi=0
flag=0
ls=[]
x=0
for i in range(N):
  x=int(input())
  ls.append(x)
  if (maxi<x):
    smaxi=maxi
    maxi=x
  elif (maxi==x):
    smaxi=maxi
  elif (smaxi<x):
    smaxi=x
for i in range(N):
  if (ls[i]==maxi):
    print(smaxi)
  else:
    print(maxi)
### BUGGY CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

#a.sort()
#c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append(s)
#    print(s)
    
#t.sort()
#print("t: ",t)

icnt=0

#import queue
#tyn3 = queue.Queue()

from collections import deque
tyn3 = deque()

# FIFOキューの作成
#    q.put(i)
#    q.get()

def pcnt(icnt,ia,t,n,tyn3,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn3)>0:
            tyn3.pop()
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia]:
        ia=ia1+1
        if not it in tyn3:
            icnt=icnt1+1
#            tyn3.put(it)
            tyn3.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)

print(icntmax)        
    

### FIXED CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

c.sort()
a.sort(key=lambda x:x[1])
#a.reverse()

icnt=0
ic2=0
for ic in range(len(c)):
    for ia in range(len(a)-1,-1,-1):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            icnt=icnt+1
            del a[ia]
            break
        else:
            continue
        break

print(icnt)
### BUGGY CODE ###

H = int(input())

cnt = H
B = [H]
for i in range(100000000000):
    cnt = cnt//2
    B.append(cnt)
    if cnt == 1:
        break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

#print(len(C))
ans= 0
for i in range(len(B)):
    ans +=C[i]
print(ans)

### FIXED CODE ###

H = int(input())
cnt = H
ans = 0
B = [H]

if H == 1:
    ans == 'NA'
else:
    for i in range(100000000000):
        cnt = cnt//2
        B.append(cnt)
        if cnt == 1:
            break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

if ans == 'NA':
    print('0')
else:
    for i in range(len(B)):
        ans +=C[i]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int, input().split())
L=[ [] for _ in range(N)]

X=[]
for _ in range(M):
    a,b = input().split()
    a=int(a)
    b=int(b)
    L[a-1].append(b)
    X.append({a:b})
Y=[ (sorted(L[_])) for _ in range(N) ]
for i in range(M) :
    for k,v in X[i].items():
        z='%06d' % (Y[k-1].index(v)+1)
        Z='%06d' % k
        print(Z+z)


### FIXED CODE ###

N,M = map(int,input().split())
L = []
for i in range(M):
    l = list(map(int,input().split()))+[i]
    L.append(l)
cnt = 0
tmp = []
M = sorted(L,key = lambda x: (x[0],x[1]))
for x in M:
    if tmp == x[0]:
        x.append(cnt+1)
        cnt += 1
    else:
        tmp = x[0]
        cnt = 0
        x.append(cnt)
M = sorted(L,key = lambda x:x[2])
#print(M)
for x in M:
    st = str(x[0]).zfill(6)
    st += str(x[3]+1).zfill(6)
    print(st)
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
S = list(set(S))
#print(S)

for i in range(1,N):
  if i in S:
    dp[i] = 1
  for j in range(len(S)):
    if i-S[j] < 1:
      break
    #print(i, S[j], i-S[j])
    dp[i] += 1*dp[i-S[j]]
    dp[i] %= mod

print(dp[-2])

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    #print(l,r)
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    #print(dp[i])
    
  dps[i] = dps[i-1] + dp[i]
  #print(dp, dps)
print(dp[-1])
### BUGGY CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    c = n
    for i in range(n):
        for j in range(i):
            if p[i] > p[j]:
                c -= 1
                break
    
    print(c)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    n = int(input())
    p = list(map(int, input().split()))
    c = 0
    mi = 2*10**5+1
    for i in range(n):
        if mi > p[i]:
            c += 1
            mi = p[i]
    
    print(c)

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

#!/usr/bin/env python3

import numpy as np

def main():
    n = int(input())
    l = list(map(int,input().split()))
    pro=1
    for num in l:
        pro = pro*num
    if pro > 10**18:
        print(-1)
    else:
        print(pro)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import numpy as np

def main():
    n = int(input())
    l = list(map(int,input().split()))
    if 0 in l:
        print(0)
        exit()
    pro=1
    for num in l:
        pro = pro*num
        if pro > 10**18:
            print(-1)
            exit()
    else:
        print(pro)

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

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

b=set(a)
ans =0
for i in b:
    c=a.count(i)
    if c>i:
        ans +=  c-i
    elif c<i:
        ans += c
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
a.append(-1)

count=1
ans=0

for i in range(0,n):
    if a[i+1]==a[i]:
        count += 1
    else:

        if count > a[i]:
            ans += count - a[i]
        elif count < a[i]:
            ans += count

        count = 1

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

import  fractions
N = int(input())
A = list(map(int,input().split()))
mod =10**9+7
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
inv_t = [0]+[1]
for i in range(2,10**7):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
  
k=1
for a in A:
  k=lcm(k,a)
  
ans=0
for a in A:
  ans+=k*inv_t[a]%mod
print(ans%mod)

### FIXED CODE ###

import  fractions
N = int(input())
A = list(map(int,input().split()))
mod =10**9+7
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
inv_t = [0]+[1]
for i in range(2,10**6+5):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
  
k=1
ans=0
for a in A:
  k=lcm(k,a)
  ans+=inv_t[a]%mod
k%=mod

print(ans*k%mod)
### BUGGY CODE ###

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

M = sum(A)
L = []
i = 1
while i <= M**0.5:
    if M%i == 0:
        L.append(i)
        L.append(M//i)
    i += 1
    
L.sort(reverse=True)

for i in L:
    temp = [0]*N
    for j in range(N):
        temp[j] = A[j]%i
    temp.sort()
    cnt = 0
    l = 0
    r = N-1
    while l < r:
        if temp[l] == 0:
            l += 1
            continue
        if temp[r] == 0:
            r -= 1
            continue
        temp[l] -= 1
        temp[r] += 1
        temp[r] %= i
        cnt += 1
    if cnt <= K:
        ans = i
        break

print(ans)

### FIXED CODE ###

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

M = sum(A)
L = []
i = 1
while i <= M**0.5:
    if M%i == 0:
        L.append(i)
        L.append(M//i)
    i += 1
    
L.sort(reverse=True)

for i in L:
    temp = [0]*N
    for j in range(N):
        temp[j] = A[j]%i
    temp.sort()
    cnt = 0
    l = 0
    r = N-1
    while l < r:
        if temp[l] == 0:
            l += 1
            continue
        if temp[r] == 0:
            r -= 1
            continue
        t = temp[l]
        temp[l] = 0
        cnt += t
        while l < r and temp[r]+t > i:
            t -= i-temp[r]
            temp[r] = 0
            r -= 1
        temp[r] += t
        temp[r] %= i
            
    if cnt <= K:
        ans = i
        break

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

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

I = N // K
n = N

for i in range(I+2):
  N = abs(N - K)
  if N < n:
    n = N

print(n)

### FIXED CODE ###

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

I = N // K
J = N % K
j = J

if J == 0:
  pass
else:
  j = J
  for i in range(I+2):
    J = abs(J - K)
    if J <= j:
      j = J
    else:
      break
      
print(j)
### BUGGY CODE ###

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        upper = 41
        #print("n={}, upper={}".format(n, upper))
        for x in range(1, upper):
            for y in range(1, upper):
                val_y = x**2 + x*y + y**2
                for z in range(1, upper):
                    if val_y + z**2 + x*z + y*z == n:
                        ans += 1
        print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        #print("n={}".format(n))
        for x in range(1, 41):
            # x==yの時
            if n - 2*x*x >= 0:
                z0 = round(sqrt(n - 2*x*x) - x)
                for z in range(z0 - 2, z0 + 3):
                    if (x + z)**2 + 2*x*x == n:
                        if x == z:
                            #print(x, x, x)
                            ans += 1
                        elif x < z:
                            #print(x, x, z)
                            ans += 3
            # x < y <= zの時
            if n - x**2 >= 0:
                upper = round(sqrt((n - x**2) / 3) - x / 3) + 5
                for y in range(x+1, upper):
                    val = x**2 + x*y + y**2
                    if (x + y)**2 - 4 * (val - n) >= 0:
                        z0 = round((-(x+y) + sqrt((x + y)**2 - 4 * (val - n))) / 2)
                        for z in range(z0-2, z0+3):
                            if z**2 + (x + y)*z + val == n:
                                if y == z:
                                    #print(x, y, z)
                                    ans += 3
                                elif y < z:
                                    #print(x, y, z)
                                    ans += 6
        print(ans)




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

INF = 10**15

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

ans_l, ans_r = INF, INF
for i in range(1, n+1):
	ans_l = min(ans_l, dp_l.Access(i) + i)
	ans_r = min(ans_r, dp_r.Access(i) - i)

print(ans_l + total_diff)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

L.sort()

tmp = 0

for i in range(N):

    for j in range(N-i-1):
        j = j + i + 1

        for k in range(N-j-1):
            k = k + j + 1

            if L[k] < L[i] + L[j]:
                tmp = tmp + 1
            else:
                break

print(tmp)


### FIXED CODE ###

# 本番では解けず。
from sys import stdin
import bisect

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

# (1)Lを昇順にソートする
L.sort()

s = 0

for i in range(N-2):
    for j in range(i+1, N-1):

        # (2)Lから2つの辺を固定で選ぶ（L[i]をa L[j]をbとする）
        # この場合、a < b + c, b < a + c はソート済みのため自明。
        # c < a + b が成り立つ棒の個数を調べる
        tmp = L[i] + L[j]

        # (3)Lの中から(2)の和(a+b)、を左に挿入できる場所二分探索で探す
        # つまりL[index - 1] < L[i] + L[j] < L[index] になるindexを探す。

        index = bisect.bisect_left(L, tmp)

        # (4) 固定で選んだ大きい方の辺から(3)で見つけた棒の間にある棒の個数を足す
        # b より右にあり、これより左にあるもの　→　開区間　(L[j], L[index])に含まれる棒は c < a + b を満たすので。
        s += (index - (j+1))

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

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

answer = 0
for i in range(len(p_li)):
    count_flag = True
    for j in range(i):
        if p_li[i] <= p_li[j]:
            continue
        else:
            count_flag = False
            break
    if count_flag:
        answer += 1

print(answer)


### FIXED CODE ###

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

answer = 0
now_min = 999999
for i in range(len(p_li)):
    if now_min > p_li[i]:
        now_min = p_li[i]
        answer += 1

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


N=int(input())
li=[input() for i in range(N)]
count=0
from collections import Counter

dic=[Counter(s.upper().replace(' ', '')) for s in li]
#print(dic)
for i in range(N):
  for j in range(i):
    if i != j:
      if dic[i]==dic[j]:
        count+=1
print(count)

### FIXED CODE ###

N=int(input())
#li=[input() for i in range(N)]
count=0
dic={}
for i in range(N):
  s=input()
  sorted_s="".join(sorted(s))
  count += dic.get(sorted_s, 0)
  dic[sorted_s] = dic.get(sorted_s, 0) + 1
print(count)
### BUGGY CODE ###

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

def Lsearch(B,key,pt):
    for i in range(len(B)-pt):
        if B[i+pt] == key:
            return i
    return -1

num,pt,n_pt,count = 1,0,0,0
while Lsearch(A,num,pt) != -1:
    n_pt = Lsearch(A,num,pt) + 1
    count += n_pt - pt -1
    pt = n_pt
    num += 1
if pt != 0:
    count += len(A) - pt
    print(count)
else:
    print(-1)


### FIXED CODE ###

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

num,pt,n_pt,count = 1,-1,0,0
while n_pt < len(A):
    if A[n_pt] == num:
        count += n_pt - pt -1
        pt = n_pt
        num += 1
    n_pt += 1
if pt != -1:
    count += len(A) - pt -1
    print(count)
else:
    print(-1)