Problem:
Sliding Minimum Element For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\{1, 7, 7, 4, 8, 1, 6\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\{1, 7, 7\}$, $\{7, 7, 4\}$, $\{7, 4, 8\}$, $\{4, 8, 1\}$, $\{8, 1, 6\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively. Constraints  $1 \leq N \leq 10^6$  $1 \leq L \leq 10^6$  $1 \leq a_i \leq 10^9$  $L \leq N$  Input The input is given in the following format. $N$ $L$ $a_1$ $a_2$ ... $a_N$  Output Print a sequence of the minimum in a line. Print a space character between adjacent elements. Sample Input 1 7 3
1 7 7 4 8 1 6 Sample Output 1 1 4 4 1 1

Solution (Python):
import collections, numbers
import random

def compute(array, window, maximize):
    if not isinstance(window, numbers.Integral):
        raise TypeError()
    if not isinstance(maximize, bool):
        raise TypeError()
    if window <= 0:
        raise ValueError("Window size must be positive")

    result = []
    deque = collections.deque()
    for i, val in enumerate(array):
        val = array[i]
        while len(deque) > 0 and ((not maximize and val < deque[-1]) or (maximize and val > deque[-1])):
            deque.pop()
        deque.append(val)

        j = i + 1 - window
        if j >= 0:
            result.append(deque[0])
            if array[j] == deque[0]:
                deque.popleft()
    return result


class SlidingWindowMinMax(object):

    def __init__(self):
        self.mindeque = collections.deque()
        self.maxdeque = collections.deque()

    def get_minimum(self):
        return self.mindeque[0]

    def get_maximum(self):
        return self.maxdeque[0]

    def add_tail(self, val):
        while len(self.mindeque) > 0 and val < self.mindeque[-1]:
            self.mindeque.pop()
        self.mindeque.append(val)

        while len(self.maxdeque) > 0 and val > self.maxdeque[-1]:
            self.maxdeque.pop()
        self.maxdeque.append(val)

    def remove_head(self, val):
        if val < self.mindeque[0]:
            raise ValueError("Wrong value")
        elif val == self.mindeque[0]:
            self.mindeque.popleft()

        if val > self.maxdeque[0]:
            raise ValueError("Wrong value")
        elif val == self.maxdeque[0]:
            self.maxdeque.popleft()

if __name__ == "__main__":
    n, l = (int(x) for x in input().split())
    array = list((int(x) for x in input().split()))

    answer = compute(array, l, False)
    print(*answer)

Solution (Python):


N,L = list(map(int, input().split()))
alist = list(map(int, input().split()))
arr = []
for i in range(L):
  while arr and alist[i] <= alist[arr[-1]]:
    arr.pop()
  arr.append(i)
for i in range(L, N):
  print(alist[arr[0]], end=' ')
  while arr and arr[0] <= i-L:
    arr.pop(0)
  while arr and alist[i] <= alist[arr[-1]]:
    arr.pop()
  arr.append(i)
print(alist[arr[0]])

Solution (Python):
import collections, numbers
import random

def compute(array, window, maximize):
    if not isinstance(window, numbers.Integral):
        raise TypeError()
    if not isinstance(maximize, bool):
        raise TypeError()
    if window <= 0:
        raise ValueError("Window size must be positive")

    result = []
    deque = collections.deque()
    for i, val in enumerate(array):
        val = array[i]
        while len(deque) > 0 and ((not maximize and val < deque[-1]) or (maximize and val > deque[-1])):
            deque.pop()
        deque.append(val)

        j = i + 1 - window
        if j >= 0:
            result.append(deque[0])
            if array[j] == deque[0]:
                deque.popleft()
    return result


if __name__ == "__main__":
    n, l = (int(x) for x in input().split())
    array = list((int(x) for x in input().split()))

    answer = compute(array, l, False)
    print(*answer)

Solution (Python):
INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()

Solution (Python):
def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini :
            mini = A[i+L-1]
        elif A[i-1] == mini :
            mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini :
            mini = A[i]
        elif A[i+L] == mini:
            mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)

Pcount = 0;
Mcount = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : Pcount += 1
        if A[i+1] < A[i] : Mcount += 1
    if Pcount > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Solution (Python):
def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Solution (Python):
from collections import deque
N, L = map(int, input().split())
A = list(map(int, input().split()))

ans = []
q = deque()

for i, a in enumerate(A):
    while q and A[q[-1]] >= a:
        q.pop()
    q.append(i)
    if i - L + 1 >= 0:
        ans.append(A[q[0]])
        if q[0] == i - L + 1:
            q.popleft()

print(*ans)

Solution (Python):
from collections import deque

N, L = map(int, input().split())
*A, = map(int, input().split())

ans = []

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i, a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Solution (Python):
import collections


def sme():
    for cur, M in enumerate(element):
        while que and M <= que[-1][1]:  
            que.pop()
        que.append((cur, M))  

        res.append(que[0][1])  

        if que and que[0][0] == cur - L + 1:  
            que.popleft()


N, L = map(int, input().split())  
element = list(map(int, input().split()))  
que = collections.deque()  
res = []  
sme()
print(*res[L - 1:])

Solution (Python):
from collections import deque

N, L = map(int, input().split())
*list, = map(int, input().split())

ans = []

que = deque()
for i, num in enumerate(list):
    while que and num <= que[-1][1]:
        que.pop()
    que.append((i, num))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Solution (Python):
from collections import deque
ans = []

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

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i,a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()
    
ans = ans[L-1:]
print(*ans)

Solution (Python):
from itertools import accumulate
from collections import deque
class SWAG:
    def __init__(self, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        self.q = deque([])
        self.accL = []
        self.accR = e_M
        self.L = self.R = 0

    def build(self,lst):
        self.q = deque(lst)
        self.L = len(lst)
        self.accL = list(accumulate(reversed(self.q),self.op_M))

    def __len__(self):
        return self.L + self.R

    def fold_all(self):
        if self.L: return self.op_M(self.accL[-1],self.accR)
        else: return self.accR

    def append(self,x):
        self.q.append(x)
        self.accR = self.op_M(self.accR,x)
        self.R += 1
    
    def popleft(self):
        if self.L:
            self.accL.pop()
            self.L -= 1
            return self.q.popleft()
        elif self.R:
            self.L,self.R = self.R-1,0
            self.accL = list(accumulate(reversed(self.q),self.op_M))
            self.accR = self.e_M
            self.accL.pop()
            return self.q.popleft()
        else:
            assert 0




import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,l,*a = [int(i) for i in read().split()]

q = SWAG(min,10**9)
q.build(a[:l])
ans = [q.fold_all()]
for i in a[l:]:
    q.popleft()
    q.append(i)
    ans.append(q.fold_all())

print(*ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class SlidingWindowAggretgation:
    def __init__(self, default = float("inf"), f = min):
        self.default = default
        self.f = f
        self.front_stack = deque()
        self.back_stack = deque()

    def get(self):
        res = self.default
        if self.front_stack:
            res = self.f(res, self.front_stack[-1][1])
        if self.back_stack:
            res = self.f(res, self.back_stack[-1][1])
        return res

    def append(self, x):
        fx = x
        if self.back_stack:
            fx = self.f(self.back_stack[-1][1], x)
        self.back_stack.append((x, fx))

    def popleft(self):
        if not self.front_stack:
            x, fx = self.back_stack.pop()
            self.front_stack.append((x, x))
            while self.back_stack:
                x, fx = self.back_stack.pop()
                fx = self.f(x, self.front_stack[-1][1])
                self.front_stack.append((x, fx))
        self.front_stack.pop()

def solve():
    n,l = LI()
    a = LI()
    swag = SlidingWindowAggretgation()
    ans = []
    for i in range(n):
        swag.append(a[i])
        if i+1 >= l:
            ans.append(swag.get())
            swag.popleft()
    print(*ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SWAG:
  def __init__(self,func,ide):
    self.ide = ide
    self.func = func
    self.front = []
    self.back = []
  
  def push(self,x):
    
    if self.back: y = self.func(self.back[-1][1],x)
    else: y = x
    self.back.append((x,y))
  
  def pop(self):
    if not self.front:
      while self.back:
        x,y = self.back.pop()
        if self.front: y = self.func(self.front[-1][1],x)
        else: y = x
        self.front.append((x,y))
    return self.front.pop()[1]
  
  def fold_all(self):
    y = self.ide
    if self.front: y = self.func(self.front[-1][1],y)
    if self.back: y = self.func(self.back[-1][1],y)
    return y
ans = []
n,l = map(int,input().split())
data = list(map(int,input().split()))
swag = SWAG(min,inf)
for i in range(l-1):
  swag.push(data[i])
for i in range(l-1,n):
  swag.push(data[i])
  ans.append(swag.fold_all())
  swag.pop()
print(*ans)

Solution (Python):
from collections import deque

def slide_min(L:int, li:list):
	deq=deque()
	ret=[]
	for i,x in enumerate(li):
		while deq and deq[-1][1]>x:
			deq.pop()
		deq.append((i,x))
		if deq[0][0]+L==i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L-1:]

def main():
	n,l,*a=map(int,open(0).read().split())
	print(*slide_min(l,a))

if __name__=="__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class SWAG(object):
    def __init__(self,dot):
        self.__front=[]
        self.__back=[]
        self.__dot=dot

    def __bool__(self):
        return True if(self.__front or self.__back) else False

    def __len__(self):
        return len(self.__front)+len(self.__back)

    def sum(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front): return back[-1][1]
        elif(not back): return front[-1][1]
        else: return self.__dot(front[-1][1],back[-1][1])

    def append(self,x):
        back=self.__back
        if(not back): back.append((x,x))
        else: back.append((x,self.__dot(back[-1][1],x)))

    def popleft(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front):
            front.append((back[-1][0],back[-1][0]))
            back.pop()
            while(back):
                front.append((back[-1][0],self.__dot(back[-1][0],front[-1][1])))
                back.pop()
        front.pop()

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    ans=[None]*n
    swag=SWAG(min)
    for i,a in enumerate(A):
        swag.append(a)
        ans[i]=swag.sum()
        if(i-k+1>=0): swag.popleft()
    print(*ans[k-1:])
resolve()

Solution (Python):
from collections import deque


if __name__ == "__main__":
    N, L = map(int, input().split())
    a = list(map(lambda x: int(x), input().split()))

    que: deque = deque()
    ans = []
    for i, elem in enumerate(a):
        while (que and elem <= que[-1][1]):
            que.pop()
        que.append((i, elem))

        ans.append(que[0][1])

        if (que and que[0][0] <= i + 1 - L):
            que.popleft()

    print(" ".join([str(elem) for elem in ans[L - 1:]]))

Solution (Python):
def ascend(x,y):
    mini = min(A[x:x+L])
    ans[x] = mini
    for i in range(x+1,y):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini
 
def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
     
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

Solution (Python):
import collections

N, L = map(int, input().split())
a = list(map(int, input().split()))
deq = collections.deque()
ans = []

for i in range(N):
    while deq and a[i] <= deq[-1][1]:deq.pop()
    deq.append((i,a[i]))
    ans.append(deq[0][1])
    if deq and deq[0][0] <=i-L+1:deq.popleft()
print(*ans[L-1:N])

Solution (Python):
import sys


def get_sliding_minimum_element(nums, k):
    res = []
    queue = []
    for i, v in enumerate(nums):
        if queue and queue[0] <= i - k:
            queue = queue[1:]
        while queue and nums[queue[-1]] > v:
            queue.pop()
        queue.append(i)
        if i + 1 >= k:
            res.append(nums[queue[0]])
    return res


b = [0 for _ in range(1000000)]
deq = [0 for _ in range(1000000)]

line = sys.stdin.readline()
n, l = map(int, line.split())
arr = list(map(int, input().split()))
s = 0
t = 0
for i in range(n):
    while s < t and arr[deq[t - 1]] >= arr[i]:
        t -= 1
    deq[t] = i
    t += 1
    if i - l + 1 >= 0:
        b[i - l + 1] = arr[deq[s]]
        if deq[s] == i - l + 1:
            s += 1

for i in range(n-l+1):
    if i == n - l:
        print(str(b[i]), end='')
    else:
        print(str(b[i]) + " ", end='')
print("\n", end='')

Solution (Python):
from collections import deque

N, L = map(int, input().split())
box = list(map(int, input().split()))

que = deque()
ans = []
for i, a in enumerate(box):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i,a))
    
    ans.append(que[0][1])
    if que and que[0][0] <= i-L+1:
        que.popleft()
        
print(*ans[L-1:])

Solution (Python):
from collections import deque

N, L = map(int, input().split())
*A, = map(int, input().split())

ans = []

que = deque()
for i, a in enumerate(A):
    while que and a <= que[-1][1]:
        que.pop()
    que.append((i, a))

    ans.append(que[0][1])

    if que and que[0][0] <= i+1-L:
        que.popleft()

print(*ans[L-1:])

Solution (Python):




from heapq import heappush, heappop


def run():
    _, size = [int(x) for x in input().split()]
    heap = []
    removed = set()
    result = []
    n = 0
    for i, v in enumerate(input().split()):
        heappush(heap, (int(v), i))
        n += 1
        if n > size:
            removed.add(i - size)
            n -= 1

        if n == size:
            while len(heap) > 0:
                minv, k = heap[0]
                if k in removed:
                    removed.remove(k)
                    heappop(heap)
                else:
                    result.append(str(minv))
                    break
    print(" ".join(result))


if __name__ == '__main__':
    run()