C. Maximum GCD Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

Your task is, for each $$$k \in \{1, \ldots, n\}$$$, to find the subsequence of length $$$k$$$ with the maximum Greatest Common Divisor.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — elements of array $$$a$$$.

Output

Output $$$n$$$ integers — the maximum Greatest Common Divisor for each $$$k$$$.

Example
Input
7
3 4 9 6 8 2 3
Output
9 4 3 3 1 1 1
Note

Elements highlighted in orange are one of the optimal subsequences:

  • $$$k=1$$$, $$$a=[3, 4, \color{orange}9, 6, 8, 2, 3]$$$.
  • $$$k=2$$$, $$$a=[3, \color{orange}4, 9, 6, \color{orange}8, 2, 3]$$$.
  • $$$k=3$$$, $$$a=[\color{orange}3, 4, \color{orange}9, \color{orange}6, 8, 2, 3]$$$.
  • $$$k=4$$$, $$$a=[\color{orange}3, 4, \color{orange}9, \color{orange}6, 8, 2, \color{orange}3]$$$.
  • $$$k=5$$$, $$$a=[3, \color{orange}4, \color{orange}9, 6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.
  • $$$k=6$$$, $$$a=[\color{orange}3, \color{orange}4, \color{orange}9, 6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.
  • $$$k=7$$$, $$$a=[\color{orange}3, \color{orange}4, \color{orange}9, \color{orange}6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.