Башня

def push(stack, elem):
    stack.append(elem)
    return elem
def top(stack):
    return stack[-1]
def pop(stack):
    return stack.pop()
def size(stack):
    return len(stack)
def power(a, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power(a * a, n // 2)
    else:
        return power(a, n - 1) * a
inf = 2 * power(10, 9) + 1
n, k = map(int, input().split())
a = [-inf] + list(map(int, input().split())) + [-inf]
p = [0] * (n + 2)
for i in range(1, n + 1):
    p[i] = p[i - 1] + a[i]
p[-1] = p[-2]
stack = []
push(stack, 0)
ans = [0] * (n + 2)
for i in range(n + 2):
    while a[top(stack)] > a[i]:
        ans[pop(stack)] = i
    push(stack, i)
imin = 1
res = [0] * (n - k + 2)
for i in range(1, n - k + 2):
    if imin < i:
        imin = i
    while ans[imin] < i + k:
        imin = ans[imin]
    res[i] = a[imin] * (p[i + k - 1] - p[i - 1])
 
#https://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3583#1

from collections import deque
 
n, k = map(int, input().split())
x, d, ssum = list(map(int, input().split())), deque(), 0
b = [(0, 0) for i in range(n)]
for i in range(n):
    ssum += x[i]
    if i >= k:
        ssum -= x[i - k]
        if d[0] == i - k:
            d.popleft()
    while len(d) and x[d[-1]] >= x[i]:
        d.pop()
    d.append(i)
    if i >= k - 1:
        nb = (b[i - k][0] + x[d[0]] * ssum, i - k + 2)
        b[i] = max(b[i - 1], nb, key=lambda x: x[0])
i = n - 1
d = []
j = b[-1][1]
d.append(str(int(j)))
while i != 0:
    i -= 1
    j1 = b[i][1]
    if j - k >= j1:
        d.append(str(int(j1)))
        j = j1
print(int(len(d)))
print(" ".join(reversed(d)))

from collections import deque
 
n, k = map(int, input().split())
x, d, ssum = list(map(int, input().split())), deque(), 0
b = [(0, 0) for i in range(n)]
for i in range(n):
    ssum += x[i]
    if i >= k:
        ssum -= x[i - k]
        if d[0] == i - k:
            d.popleft()
    while len(d) and x[d[-1]] >= x[i]:
        d.pop()
    d.append(i)
    if i >= k - 1:
        nb = (b[i - k][0] + x[d[0]] * ssum, i - k + 2)
        b[i] = max(b[i - 1], nb, key=lambda x: x[0])
i = n - 1
d = []
j = b[-1][1]
d.append(str(int(j)))
while i != 0:
    i -= 1
    j1 = b[i][1]
    if j - k >= j1:
        d.append(str(int(j1)))
        j = j1
print(int(len(d)))
print(" ".join(reversed(d)).format(d))

v = int(len(d))
print(v)
print(" ".join(map(str, d)) + "\n")

from collections import deque
 
n, k = map(int, input().split())
x, d, ssum = list(map(int, input().split())), deque(), 0
b = [(0,0) for i in range(n)]
for i in range(n):
    ssum += x[i]
    if i >= k :
        ssum -= x[i - k]
        if d[0] == i - k :
            d.popleft()
    while len(d) and x[d[-1]] >= x[i]:
        d.pop()
    d.append(i)
    if i >= k - 1:
        nb = (b[i-k][0] + x[d[0]] * ssum, i-k+2)
        b[i] = max(b[i-1], nb, key=lambda x: x[0])
i = n - 1
d = deque()
j = b[-1][1]
d.appendleft(j)
while i !=0:
    i -= 1
    j1 = b[i][1]
    if j-k>=j1 and j1 > 0 :
        d.appendleft(j1)
        j = j1
print(str(len(d)))
print(" ".join(map(str, d)))