from collections import deque, namedtuple


QItem = namedtuple('QItem', 'index, value')


class MaxQueue:
    def __init__(self, k):
        self.k = k
        self.xs = deque()

    def sanitize(self, i: int):
        """pop the leftmost item if its index is out of reach"""
        if self.xs and self.xs[0].index <= i - self.k:
            self.xs.popleft()

    def push(self, qitem: QItem):
        self.sanitize(qitem.index)
        while self.xs and self.xs[-1].value < qitem.value:
            self.xs.pop()
        self.xs.append(qitem)

    def max(self):
        return self.xs[0].value


def max_k_queue(xs, k):
    res = []
    mq = MaxQueue(k)
    for i, x in enumerate(xs):
        mq.push(QItem(i, x))
        if i >= k-1:
            res.append(mq.max())
    return res


def main():
    _test()
    print("ok")


def _test():
    assert max_k_queue([10, 5, 2, 7, 8, 7], 3) == [10, 7, 8, 8]
    assert max_k_queue([10, 5, 2, 7, 8, 7], 6) == [10]
    assert max_k_queue([1, 2, 3, 4], 1) == [1, 2, 3, 4]


if __name__ == '__main__':
    main()