Farmer John's N (1≤N≤105 ) cows have been arranged into a line. The i
th cow has label ai (1≤ai ≤N). A group of cows can form a friendship group if they all have the same label and each cow is within x cows of all the others in the group, where x is an integer in the range [1,N]. Every cow must be in exactly one friendship group.
For each x from 1 to N , calculate the minimum number of friendship groups that could have formed.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line consists of an integer N.
The next line contains a1...aN , the labels of each cow.
OUTPUT FORMAT (print output to the terminal / stdout):
For each x from 1 to N , output the minimum number of friendship groups for that x on a new line.
SAMPLE INPUT:
9
1 1 1 9 2 1 2 1 1
SAMPLE OUTPUT:
7
5
4
4
4
4
4
3
3
Here are examples of how to assign cows to friendship groups for x=1
and x=2 in a way that minimizes the number of groups. Each letter corresponds to a different group.
SCORING:
Inputs 2-3: N≤5000
Inputs 4-7: ai≤10 for all i
Inputs 8-11: No label appears more than 10 times.
Inputs 12-20: No additional constraints.
Problem credits: Chongtian Ma
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
