← 返回 walmartlabs 的题目列表Shortest Complete Talent Team Starting at Each Index
类型：online_judge
Problem: Shortest Complete Talent Team Starting at Each Index
There are n students in a class, arranged in an array. Each student has exactly one talent, represented by an integer. There are talentsCount different talents, numbered from 1 to talentsCount.
You need to form a team such that:
The team consists of a contiguous segment of students;
The team contains all talentsCount talent types at least once.
For every possible starting index i, return the length of the shortest contiguous subarray starting at i that contains all talent types. If it is impossible to collect all talents starting from i, return -1.
Input Format
n talentsCount
talent[0] talent[1] ... talent[n-1]
Output Format
Print n integers, where the i-th integer is the shortest valid length starting from index i.
Constraints
1 <= n <= 10^5
1 <= talentsCount <= 10^5
1 <= talent[i] <= talentsCount
Expected time complexity: O(n) or close to O(n).
Example
Input:
5 3
1 2 3 2 1
Output:
3 4 3 -1 -1
Example
Input
5 3
1 2 3 2 1
Output
3 4 3 -1 -1