Башня

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())
l = list(map(int, input().split()))
s = sum(l[:k])
res = deque([[1]], k)
d = deque([s], k)
for i in range(1, n - k + 1):
    s += l[k + i - 1] - l[i - 1]
    a, b = d[-1], s + (d[0] if i >= k else 0)
    if a > b:
        d.append(a)
        res.append(res[-1])
    else:
        d.append(b)
        res.append((res[0] if i >= k else []) + [i + 1])
print(len(res[-1]))
print(*res[-1])

import sys
 
def get_vals(n, arr, rev):
    if rev:
        arr.reverse()
 
    st = []
    vals = [0 for i in range(n)]
    for i in range(n):
        while len(st) != 0 and arr[st[-1]] >= arr[i]:
            st.pop()
        vals[i] = (i + 1) * arr[i] if len(st) == 0 else (i - st[-1]) * arr[i] + vals[st[-1]]
        st.append(i)
 
    if rev:
        arr.reverse()
        vals.reverse()
 
    return vals
 
def main():
    n = int(input())
    arr = list(map(int, input().split()))
 
    lf = get_vals(n, arr, False)
    rf = get_vals(n, arr, True)
 
    val, pos = max(((lf[i] + rf[i] - arr[i], i) for i in range(n)))
    for i in range(pos - 1, -1, -1):
        arr[i] = min(arr[i], arr[i + 1])
    for i in range(pos + 1, n):
        arr[i] = min(arr[i], arr[i - 1])
 
    print(" ".join(map(str, arr)) + "\n")
 
main()