require 'set'
n = gets.to_i
left_nodes = Set[0]
right_nodes = Set.new
g = {?s => Set[0], 0 => Set.new}

def augument_path(g)
    queue = [?s]
    reached = Set[?s]
    prev = {}
    until queue.empty?
        u = queue.shift
        g[u].each do |v|
            next if reached.include?(v)
            prev[v] = u
            reached << v
            queue << v
        end
        break if prev[?t]
    end
    if prev[?t]
        path = [?t]
        v = path[0]
        while u = prev[v]
            path.unshift(u)
            v = u
        end
        return path
    end
    return nil
end

k = 0
(1..n).each do |j|
    i = gets.to_i
    if left_nodes.include?(i)
        right_nodes << j
        g[j] = Set[?t]
        g[i] << j
    else
        left_nodes << j
        g[?s] << j
        g[j] = Set[i]
    end
    path = augument_path(g)
    if path
        k += 1
        path.each_cons(2) do |u, v|
            g[u].delete(v)
            (g[v] ||= Set.new) << u
        end
    end
    p k
end

