Salary Raise Partition

Bytecorp had a tough year in 2022. In order to justify that employees do not deserve a raise, the HR department devised a method based on the income sequence generated by an employee over consecutive days. In Byteotia a year can have any number of days. The idea is to partition the given income sequence into k contiguous segments such that it is impossible to choose one element from each segment that forms a strictly increasing sequence.

More formally, let the income sequence be A[1], A[2], ..., A[n]. We want to split the sequence into k non-empty contiguous segments. A segmentation is considered valid if there does not exist a choice of indices i₁, i₂, ..., i_k with i_j belonging to the j^th segment and satisfying

[ A[i_1] < A[i_2] < \cdots < A[i_k]. ]

It can be shown that a valid partition exists if and only if the length of the longest increasing subsequence (LIS) of the entire sequence is less than k. Your task is to determine such a segmentation if it exists, or output -1 otherwise.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10⁵), where n is the length of the income sequence and k is the number of segments to form. The second line contains n space‐separated integers A[1], A[2], …, A[n] representing the income sequence. Each integer fits in a 32‐bit signed integer.

outputFormat

If a valid partition exists, output k space-separated positive integers representing the lengths of the segments (in order). Otherwise, output -1.

sample

3 3
1 2 3

-1