codeforces#P1488G. Painting Numbers

    ID: 31838 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 9 上传者: 标签>*special problemdata structuresgreedynumber theory*2500

Painting Numbers

Description

You are given $n$ integers, each integer is from $1$ to $n$, all of them are pairwise distinct. You have to paint them red and blue (each integer should have exactly one color).

The cost of painting is the number of pairs $(x, y)$ such that $y \bmod x = 0$, $y$ is red and $x$ is blue.

For each $k \in [1, n]$, calculate the maximum cost of painting if exactly $k$ integers should have a red color.

The first line contains one integer $n$ ($2 \le n \le 10^5$).

For each $k \in [1,n]$ print one integer — the maximum cost of painting, if exactly $k$ integers should be red.

Input

The first line contains one integer $n$ ($2 \le n \le 10^5$).

Output

For each $k \in [1,n]$ print one integer — the maximum cost of painting, if exactly $k$ integers should be red.

Samples

6
3 5 6 6 5 0
2
1 0
11
3 6 9 11 12 13 14 14 13 10 0