Problem:
 Score : 900 points    Problem Statement There are N squares in a row. The squares are numbered 1, 2, ..., N from left to right.  You have two pieces, initially placed on square A and B , respectively.
You will be asked to process Q queries of the following kind, in the order received:   Given an integer x_i , move one of the two pieces of your choice to square x_i .   Here, it takes you one second to move a piece one square.
That is, the time it takes to move a piece from square X to Y is |X-Y| seconds.  Your objective is to process all the queries in the shortest possible time.  You may only move the pieces in response to queries, and you may not move both pieces at the same time.
Also, it is not allowed to rearrange the order in which queries are given.
It is, however, allowed to have both pieces in the same square at the same time.      Constraints  1 ≤ N, Q ≤ 200,000  1 ≤ A, B ≤ N  1 ≤ x_i ≤ N         Input Input is given from Standard Input in the following format:  N  Q  A  B  x_1  x_2 ... x_Q       Output Let the shortest possible time to process all the queries be X seconds. Print X .        Sample Input 1 8 3 1 8
3 5 1      Sample Output 1 7  All the queries can be processed in seven seconds, by:   moving the piece at square 1 to 3  moving the piece at square 8 to 5  moving the piece at square 3 to 1        Sample Input 2 9 2 1 9
5 1      Sample Output 2 4  The piece at square 9 should be moved first.       Sample Input 3 9 2 1 9
5 9      Sample Output 3 4  The piece at square 1 should be moved first.       Sample Input 4 11 16 8 1
1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7      Sample Output 4 21

Solution (Python):
import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		
		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

	
	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:])))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q,A,B,*X = map(int,read().split())

class MinSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) 
        
    def build(self,raw_data):
        
        INF = 10**18
        self.data = [INF] * (2*self.size)
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        
        L += self.size
        R += self.size + 1
        
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x > y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x > y: x = y
            L >>= 1; R >>= 1
        return x

INF = 10**18
dpL = MinSegTree(N+10); dpL.build([INF] * (N+10))
dpR = MinSegTree(N+10); dpR.build([INF] * (N+10))
dpL.update(A,0-A)
dpR.update(A,0+A)

prev_x = B
add = 0
for x in X:
    from_left = dpL.get_value(0,x) + x
    from_right = dpR.get_value(x,N+10) - x
    dist = x-prev_x if x>prev_x else prev_x-x
    y = from_left if from_left < from_right else from_right
    y -= dist
    dpL.update(prev_x,y-prev_x)
    dpR.update(prev_x,y+prev_x)
    add += dist
    prev_x = x

dp = [(x+y)//2 for x,y in zip(dpL.data[dpL.size:],dpR.data[dpR.size:])]
answer = min(dp) + add
print(answer)