def suf_max(xs):
    for i in range(len(xs)-2, -1, -1):
        xs[i] = max(xs[i+1], xs[i])


class MaxSegment:
    def __init__(self, xs):
        self.xs = xs[:]
        self._local_max = 0
        self._reset()

    def _reset(self):
        suf_max(self.xs)
        self._last = 0
        self._local_max = self.xs[0]

    def push(self, x):
        if self._last == len(self.xs) - 1:
            self.xs[-1] = x
            self.xs.reverse()
            self._reset()
        else:
            self.xs[self._last] = x
            self._last += 1
            self._local_max = max(x, self.xs[self._last])

    def max(self):
        return self._local_max


def max_k_segments(xs, k):
    result = []
    ms = MaxSegment(xs[:k])
    for x in xs[k:]:
        result.append(ms.max())
        ms.push(x)
    result.append(ms.max())
    return result


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


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


if __name__ == '__main__':
    main()