Данияр — храбрый рыцарь, сражающийся с $$$n$$$ монстрами, которые расположены в ряд. $$$i$$$-й монстр слева имеет силу $$$a_i$$$.

У Данияра есть меч длины $$$k$$$, который позволяет убить не более чем $$$k$$$ последовательных монстров одним махом. После того как он убивает монстров, оставшиеся монстры продвигаются вперед, снова замыкая ряд.

Однако, Данияр может размахнуть свой меч не более $$$m$$$ раз прежде чем устанет и не сможет продолжать бой.

Главная цель Данияра — победить сильнейших монстров до того, как он слишком устанет, чтобы продолжать битву. Поэтому он хочет минимизировать силу самого сильного монстра, который все еще будет жив после этой битвы.

К сожалению, прямо перед битвой Данияр сломал свой меч. Чтобы решить эту проблему, ему необходимо срочно отправиться к ближайшему кузнецу, чтобы купить новый меч. Однако он не уверен в длине меча, который ему стоит приобрести. Он хочет определить минимальную силу самого сильного монстра, который все еще будет жив, если бы у него был меч длины $$$k$$$ для каждого возможного значения $$$k$$$ ($$$1 \le k \le n$$$).