Page not loading? Try clicking here.
Placeholder

#8185
Subtask

독사 연합 2s 1024MB

Problems

Farmer John's N cows have been arranged into a line. The ith cow has label a_i. 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

The first line consists of an integer N.

The next line contains a_1...a_N, the labels of each cow.


Output

For each x from 1 to N, output the minimum number of friendship groups for that x on a new line.


Subtask

# Score Condition
#110

N \le 5000

#220

a_i \le 10

#330

No label appears more than 10 times.

#440

No additional constraints


Example 

9
1 1 1 9 2 1 2 1 1
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.

Example:

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 groups)
x = 1: A A B C D E F G G (7 groups, alternative grouping)
x = 2: A A A B C D C E E (5 groups)
x = 2: A A A B C D C D E (5 groups, alternative grouping)

Source

USACO 2024 December Gold

You must sign in to write code.