Good Intervals Count

You are given a sequence \(a\) of length \(n\) containing distinct elements, and an integer \(k\). For an interval \([l, r]\) (1-indexed) the interval is defined as good if it satisfies the following conditions:

1. Define the sequence \[ b = \{a_l, \max(a_l, a_{l+1}), \max(a_l, a_{l+1}, a_{l+2}), \dots, \max(a_l, a_{l+1}, \dots, a_r)\} \] and then remove duplicate consecutive elements (equivalently, the record sequence when scanning from \(l\) to \(r\)). Let \(\ell\) be the length of the resulting sequence. It must hold that \(1 < \ell \le k\).
2. The maximum element in the interval occurs at the last position, i.e., \(\max(a_l,a_{l+1},\dots,a_r)=a_r\).

Your task is to compute, for every index \(i\) (\(1 \le i \le n\)), the number of good intervals \([l, r]\) with \(l \le i \le r\).

inputFormat

The first line contains two integers \(n\) and \(k\) (the length of the sequence and the upper bound for the record count).

The second line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\), representing the sequence.

outputFormat

Output \(n\) integers separated by spaces. The \(i\)-th integer is the number of good intervals \([l, r]\) such that \(l \le i \le r\).

sample

5 2
3 1 2 5 4

2 3 5 4 2