Nodir, Gavhar, Gulnoza, Yahyo and Umid together founded the company NGGYU™. The company's main priority is solving problems about MEX.
MEX – Minimum Excluded – is the smallest non-negative integer that does not occur in the array. For example, \(MEX([1, 2, 0, 5]) = 3\) and \(MEX([1, 3]) = 0\).
You are given an array \(a[1], a[2], \dots, a[N]\) consisting of \(N\) elements.
For a given number \(k\), you may split the array \(a\) into several parts. If the MEX value of every part does not exceed \(k\), the split is called good. Let \(f(k)\) denote the minimum number of parts in a good split.
Find the value of \(f(k)\) for all \(1 \le k \le N\).
The first line contains the number \(N\).
The second line contains \(a[1], a[2], \dots, a[N]\).
Print a single line with \(N\) integers – \(f(1), f(2), \dots, f(N)\).
For example, let \(N = 8\) and \(a = [0, 1, 1, 2, 0, 2, 1, 0]\).
\(f(1) = 5\), because the array can be split into \(5\) parts as \([0]; [1, 1, 2]; [0, 2]; [1]; [0]\).
\(f(2) = 3\), because the array can be split into \(3\) parts as \([0, 1, 1]; [2, 0, 2]; [1, 0]\).
8 0 1 1 2 0 2 1 0
5 3 1 1 1 1 1 1