#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int lim = 3e4 + 5;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, w[lim];
const int INF = 1e9;
namespace sub1{
int dp[1 << 10][10];
void solve(){
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = w[1];
for(int mask = 1; mask < (1 << n); mask++){
for(int i = 0; i < n; i++){
if(mask >> i & 1){
if(i + 1 < n){
minimize(dp[mask | (1 << (i + 1))][i + 1], dp[mask][i] + w[i + 2]);
}
for(int x = 0; x < n; x++){
if(mask >> x & 1){
for(int y = x; y < n; y++){
if(mask >> y & 1){
int t = (x + 1) * (y + 1);
if(t <= n){
minimize(dp[mask | (1 << (t - 1))][t - 1], dp[mask][i] + w[t]);
}
}
}
}
}
}
}
}
for(int i = 0; i < n; i++){
int ans = INF;
for(int mask = 0; mask < (1 << n); mask++){
if(mask >> i & 1){
minimize(ans, dp[mask][i]);
}
}
cout << ans << "\n";
}
}
}
namespace sub234{
const int lim = 1402;
const int CV = 11;
int fmask[1 << CV], idp[1 << CV][CV], f[1 << CV][38][lim >> 1];
vector<int>divi[lim];
int dp(int mask, int a, int b){
if(a == b){
a = 1;
}
int& ans = f[mask][a][b];
if(ans != -1){
return ans;
}
if(b <= CV){
return ans = fmask[mask | (1 << (a - 1)) | (1 << (b - 1))];
}
ans = dp(mask, a, b - 1) + 1;
for(int x : divi[b]){
int y = b / x, aa = a;
if(x < aa){
swap(x, aa);
}
if(x > y){
swap(x, y);
}
minimize(ans, dp(mask | (1 << (aa - 1)), x, y) + 1);
}
return ans;
}
void solve(){
memset(idp, 0x3f, sizeof(idp));
for(int mask = idp[1][0] = 1; mask < (1 << CV); mask++){
for(int i = 0; i < CV; i++){
if(mask >> i & 1){
if(i + 1 < CV){
minimize(idp[mask | (1 << (i + 1))][i + 1], idp[mask][i] + 1);
}
for(int x = 0; x < CV; x++){
if(mask >> x & 1){
for(int y = x; y < CV; y++){
if(mask >> y & 1){
int t = (x + 1) * (y + 1);
if(t <= CV){
minimize(idp[mask | (1 << (t - 1))][t - 1], idp[mask][i] + 1);
}
}
}
}
}
}
}
fmask[mask] = *min_element(idp[mask], idp[mask] + CV);
}
for(int mask = (1 << CV) - 1; mask > -1; mask--){
for(int i = 0; i < CV; i++){
minimize(fmask[mask], fmask[mask | (1 << i)]);
}
}
memset(f, -1, sizeof(f));
for(int i = 2; i * i < lim; i++){
for(int j = i * i; j < lim; j += i){
divi[j].push_back(i);
}
}
for(int i = 1; i <= n; i++){
int ans = i;
for(int j = 0; j < i; j++){
int b = i - j;
for(int& x : divi[b]){
int y = b / x;
minimize(ans, dp(0, x, y) + j + 1);
}
}
cout << ans * w[1] << "\n";
}
}
}
namespace sub56{
const int CV = 7;
const int E[4] = {(1 << CV) | 1, 14, 32, 174};
const int CNT_STATE = 13237016;
int fid[(1 << CV) | 1][14][32][174], fmask[1 << CV], idp[1 << CV][CV], f[CNT_STATE];
vector<int>divi[lim];
int dp(int mask, int a, int b, int c, int d){
for(int _ = 0; _ < 3; _++){
if(a > b){
swap(a, b);
}
if(b > c){
swap(b, c);
}
if(c > d){
swap(c, d);
}
}
int na = a, nb = b, nc = c, nd = d;
if(b == a){
a = 1;
}
if(c == b){
b = 1;
}
if(d == c){
c = 1;
}
for(int _ = 0; _ < 3; _++){
if(a > b){
swap(a, b);
}
if(b > c){
swap(b, c);
}
if(c > d){
swap(c, d);
}
}
int& ans = f[fid[mask][a][b][c] + d - 1];
if(ans != -1){
return ans;
}
if(d <= CV){
return ans = fmask[mask | (1 << (a - 1)) | (1 << (b - 1)) | (1 << (c - 1)) | (1 << (d - 1))];
}
ans = dp(mask, a, b, c, d - 1);
for(int x : divi[d]){
int y = d / x;
if(x <= a){
minimize(ans, dp(mask | (1 << (x - 1)), a, b, c, y));
}
else{
minimize(ans, dp(mask | (1 << (a - 1)), x, b, c, y));
}
}
return ans += w[d];
}
void solve(){
for(int mask = 0, cnt = 0; mask < E[0]; mask++){
for(int i = 1; i < E[1]; i++){
for(int j = i; j < E[2]; j++){
for(int k = j; k < E[3]; k++){
int x = i * j * k;
for(int t = 0; t < 7; t++){
if(mask >> t & 1){
x *= t + 1;
}
}
fid[mask][i][j][k] = cnt;
cnt += lim / x + 1;
}
}
}
}
memset(f, -1, sizeof(f));
for(int i = 2; i * i < lim; i++){
for(int j = i * i; j < lim; j += i){
divi[j].push_back(i);
}
}
memset(idp, 0x3f, sizeof(idp));
idp[1][0] = w[1];
for(int mask = 1; mask < (1 << CV); mask++){
for(int i = 0; i < CV; i++){
if(mask >> i & 1){
if(i + 1 < CV){
minimize(idp[mask | (1 << (i + 1))][i + 1], idp[mask][i] + w[i + 2]);
}
for(int x = 0; x < CV; x++){
if(mask >> x & 1){
for(int y = x; y < CV; y++){
if(mask >> y & 1){
int t = (x + 1) * (y + 1);
if(t <= CV){
minimize(idp[mask | (1 << (t - 1))][t - 1], idp[mask][i] + w[t]);
}
}
}
}
}
}
}
fmask[mask] = *min_element(idp[mask], idp[mask] + CV);
}
for(int mask = (1 << CV) - 1; mask > -1; mask--){
for(int i = 0; i < CV; i++){
minimize(fmask[mask], fmask[mask | (1 << i)]);
}
}
for(int i = 1; i <= n; i++){
cout << dp(0, 1, 1, 1, i) << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> w[i];
}
if(n <= 10){
sub1::solve();
}
else if(n <= 1400 && count(w + 1, w + n + 1, w[1]) == n){
sub234::solve();
}
else{
sub56::solve();
}
}
