Башня

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 = deque()
for i in range(k) :
    b.append(0)
    b.append(deque())
for i in range(n):
    if k == 1:
        res = [int(i) for i in range(1,n+1)]
        break
    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:
        bls = b.popleft()
        bli = deque(b.popleft())
        bri = b.pop()
        brs = b[-1]
        b.append(bri)
        if brs > bls + x[d[0]] * ssum :
            b.append(brs)
            b.append(bri)
        else :
            bli.append(i-k+2)
            b.append(bls + x[d[0]] * ssum)
            b.append(bli)
if k != 1 :
    res = b[-1]
print(len(res))
print(*res)

from collections import deque
 
 
n, k = map(int, input().split())
x = list(map(int, input().split()))
res = [(0, []) for _ in range(k)]
d = deque()
tmp = 0
for i in range(n):
    while d and x[d[-1]] >= x[i]:
        d.pop()
    d.append(i)
    tmp += x[i]
    if i >= k - 1:
        if i > k - 1:
            if d[0] == i - k:
                d.popleft()
            tmp -= x[i - k]
            mb1 = res[(i - k) % k]
            mb2 = res[(i - 1) % k]
            if mb2[0] >= mb1[0] + tmp * x[d[0]]:
                res[i % k] = mb2
            else:
                res[i % k] = (mb1[0] + tmp * x[d[0]], mb1[1] + [i - k + 2])
        else:
            res[i] = tmp * x[d[0]], res[i - k][1] + [i - k + 2]
ans = res[i % k][1]
print(len(ans))
print(*ans)