問題文

315国の首都はビル街になっており、大通りには道路に面するように一直線上に $N+2$ 個のビルが並んでいます。
ビルの高さを左から順に $a_1, a_2, \cdots, a_{N+2}$ とするとき、現在のビルの高さは $a_1=a_{N+2}=2 \cdot 10^9, a_i=1(1 < i < N+2)$ となっています。
315国は普段から人の通りが多く混雑しており、原因を調査したところビル間を移動する人々が大通りを利用することが原因でした。
そこで、ビルを増築し、間に遊歩道を作ることで混雑を緩和しようとしました。
ビルの増築は、以下の手順で行います。
まず、 $1 < i < N+2$ を満たす各 $i$ について、 $i$ 番目のビルの高さ $a_i$ を $1$ 以上 $10^9$ 以下の値だけ増やします。
その後、各ビルについて自分より左側と右側にある自分以上の高さを持つビルのうち、一番近いビルとの間に遊歩道を作ります。この遊歩道は2つのビル間を双方向に移動することができます。
さて、今ビル $i$ から最小の数の遊歩道のみを使ってビル $j$ に向かうときに使った遊歩道の数を $d_{ij}$ とすると、混雑度は $\sum_{i=2}^{N+1} \sum_{j=2}^{N+1} d_{ij}$ で表されます。
このとき、混雑度が最小になるようなビルの建て方を一つ出力してください。

入力

$N$

• $1 \leq N \leq 2000$

出力

増築後の各ビルの高さを空白区切りで出力してください。
最後に改行してください。

サンプル

1

2000000000 1000000001 2000000000

2

2000000000 315 36000 2000000000