package contest191018; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class F { InputStream is; PrintWriter out; String INPUT = ""; void solve() { // 左a, 右b // (a+b+1)^2 + sa+sb+mine // a^2+b^2+1+2a+2b+2ab+sa+sb+mine // a^2+1+2a+sa+mine + b^2+2b + 2ab + sb int n = ni(); long[] a = new long[n]; for(int i = 0;i < n;i++) { a[i] = nl(); } ans = new long[n]; Arrays.fill(ans, Long.MAX_VALUE); dfs(0, n, a); for(long v : ans) { out.println(v); } } long[] ans; void dfs(int l, int r, long[] a) { if(r-l == 1) { ans[l] = Math.min(ans[l], a[l]+1); return; } int h = l+r>>1; { long sum = 0; EnvelopeLinear el = new EnvelopeLinear(r-h+1); // EnvelopeLinearDeque el = new EnvelopeLinearDeque(r-h+1); long[][] si = new long[r-h][]; int p = 0; for(int i = h;i < r;i++) { sum += a[i]; si[p++] = new long[] {2L*(i-h+1), (long)(i-h+1)*(i-h+1) + sum}; } for(int i = p-1;i >= 0;i--) { el.add(si[i][0], si[i][1]); } // (l+r)^2 + sl + sr // r^2 + 2lr + l^2 sum = 0; for(int i = h-1;i >= l;i--) { sum += a[i]; // long val = sum + (long)(h-i)*(h-i) + el.get(h-i); long val = sum + (long)(h-i)*(h-i) + el.min(h-i); ans[i] = Math.min(ans[i], val); } for(int i = l+1;i < h;i++) { ans[i] = Math.min(ans[i], ans[i-1]); } } { long sum = 0; EnvelopeLinear el = new EnvelopeLinear(h-l); // EnvelopeLinearDeque el = new EnvelopeLinearDeque(r-h+1); long[][] si = new long[h-l][]; int p = 0; for(int i = h-1;i >= l;i--) { sum += a[i]; si[p++] = new long[] {2L*(h-i), (long)(h-i)*(h-i) + sum}; } for(int i = p-1;i >= 0;i--) { el.add(si[i][0], si[i][1]); } // (l+r)^2 + sl + sr // r^2 + 2lr + l^2 sum = 0; for(int i = h;i < r;i++) { sum += a[i]; // long val = sum + (long)(h-i)*(h-i) + el.get(h-i); long val = sum + (long)(i-h+1)*(i-h+1) + el.min(i-h+1); ans[i] = Math.min(ans[i], val); } for(int i = r-2;i >= h;i--) { ans[i] = Math.min(ans[i], ans[i+1]); } } dfs(l, h, a); dfs(h, r, a); } public static class EnvelopeLinearDeque { public long[] slopes, intercepts; public int f, b; public EnvelopeLinearDeque(int n) { slopes = new long[n]; intercepts = new long[n]; f = b = 0; } public long f(long x, int ind) { return slopes[ind]*x+intercepts[ind]; } public double f(double x, int ind) { return slopes[ind]*x+intercepts[ind]; } public boolean strictLesser(int a, int b, long num, long den) { double x = (double)num/den; double cha = f(x, a) - f(x, b); if(Math.abs(cha) < 1e-9){ return (slopes[a]*num+intercepts[a]*den) - (slopes[b]*num+intercepts[b]*den) < 0; }else{ return cha < 0; } } public long get(long x) { while(f-b > 1 && f(x, b) > f(x, b+1))b++; return f(x, b); } public void add(long slope, long intercept) { if(f-b > 0)assert slope <= slopes[f-1]; if(f-b > 0 && slope == slopes[f-1] && intercept >= intercepts[f-1])return; // sl*x+in = lsl*x+lin // (sl-lsl)*x = lin-in while(f-1-b > 0 && strictLesser(f-2, f-1, intercept-intercepts[f-1], slopes[f-1] - slope)){ f--; } slopes[f] = slope; intercepts[f] = intercept; f++; } } public static class EnvelopeLinear { public static final long INF = Long.MIN_VALUE; public long[] xs; public long[] intercepts, slopes; public int p; public EnvelopeLinear(int n) { xs = new long[n]; intercepts = new long[n]; slopes = new long[n]; p = 0; } public void clear() { p = 0; } public void add(long slope, long intercept) { assert p == 0 || slopes[p-1] >= slope; while(p > 0){ int i = p-1; if(p > 1 && intercept+xs[i]*slope <= intercepts[i]+xs[i]*slopes[i]){ // x=xs[i] p--; continue; } if(slope == slopes[i]){ if(intercept >= intercepts[i]){ return; }else{ p--; continue; } } // y=sx+i vs y=Sx+I // sx+i=Sx+I // x=(i-I)/(S-s) long num = intercept-intercepts[i]; long den = slopes[i]-slope; long nx = num < 0 ? num/den : (num+den-1)/den; xs[p] = nx; intercepts[p] = intercept; slopes[p] = slope; p++; return; } xs[p] = INF; intercepts[p] = intercept; slopes[p] = slope; p++; } public int argmin(int x) { if(p <= 0)return -1; int ind = Arrays.binarySearch(xs, 0, p, x); if(ind < 0)ind = -ind-2; return ind; } public long min(long x) { if(p <= 0)return Long.MIN_VALUE; int ind = Arrays.binarySearch(xs, 0, p, x); if(ind < 0)ind = -ind-2; return slopes[ind]*x + intercepts[ind]; } } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new F().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }