#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } ////////////////////////////////////////////////////// using Real=double; using Point=complex; const Real EPS=1e-10; const Real pi=acosl(-1); //入出力補助 istream &operator>>(istream &is,Point &p){ Real a,b; is>>a>>b; p=Point(a,b); return is; } ostream &operator<<(ostream &os,Point &p){ return os<EPS) return 1;//COUNTER CLOCKWISE else if(cross(b,c)<-EPS) return -1;//CLOCKWISE else if(dot(b,c)<0) return 2;//c--a--b ONLINE BACK else if(norm(b)EPS or abs(cross(l1.p2-l1.p1,l2.p2-l1.p1))EPS) return 0; Real d1=abs(c.center-l.p1),d2=abs(c.center-l.p2); //線分が円内 if(d1c.r+EPS) or (d2c.r+EPS)) return 1; //円の外部にまるまるはみ出ていないか if(dot(l.p1-h,l.p2-h)<0) return 2; return 0; } //円と円の位置関係,共通接線の個数を返す int intersect(Circle c1,Circle c2){ if(c1.r crosspoint(Circle c,Line l){ vector ret; Point h=projection(l,c.center); Real d=sqrt(c.r*c.r-norm(h-c.center)); Point e=(l.p2-l.p1)*(1/abs(l.p2-l.p1)); if(c.r*c.r+EPS crosspoint(Circle c,Segment s){ Line l=Line(s.p1,s.p2); int ko=intersect(c,s); if(ko==2) return crosspoint(c,l); vector ret; if(ko==0) return ret; ret=crosspoint(c,l); if(ret.size()==1) return ret; vector rret; //交点で挟める方を返す if(dot(s.p1-ret[0],s.p2-ret[0])<0) rret.push_back(ret[0]); else rret.push_back(ret[1]); return rret; } //v vector crosspoint(Circle c1,Circle c2){ vector ret; int isec=intersect(c1,c2); if(isec==0 or isec==4) return ret; Real d=abs(c1.center-c2.center); Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d)); Real t=atan2(c2.center.imag()-c1.center.imag(),c2.center.real()-c1.center.real()); ret.push_back(c1.center+Point(cos(t+a)*c1.r,sin(t+a)*c1.r)); ret.push_back(c1.center+Point(cos(t-a)*c1.r,sin(t-a)*c1.r)); return ret; } //v //点pから引いた円cの接線の接点を返す vector tangent(Circle c,Point p){ return crosspoint(c,Circle(p,sqrt(norm(c.center-p)-c.r*c.r))); } //v //二円の共通接線,Lineの2点は接点を表す vector tangent(Circle c1,Circle c2){ vector ret; if(c1.r0){ Point uu=u*h,vv=v*sqrt(1-h*h); ret.push_back(Line(c1.center+(uu+vv)*c1.r,c2.center-(uu+vv)*c2.r*s)); ret.push_back(Line(c1.center+(uu-vv)*c1.r,c2.center-(uu-vv)*c2.r*s)); } } return ret; } //v //最小包含円を返す 計算量は期待値O(n) Circle MinimumBoundingCircle(vector v){ int n=v.size(); //ランダムシャッフル.いぢわるされたくないもんだ mt19937 mt(time(0)); shuffle(v.begin(),v.end(),mt); Circle ret(0,0); //2点で円を作る auto make_circle2=[&](Point a,Point b){ return Circle((a+b)*0.5,dis(a,b)/2); }; //3点で円を作る auto make_circle3=[&](Point A,Point B,Point C){ Point cent=circumcenter(A,B,C); return Circle(cent,dis(cent,A)); }; auto isIn=[&](Point a){ return dis(ret.center,a) ps){ sort(ALL(ps),[&](Point a,Point b){ return real(a) rec=[&](int l,int r){ if(r-l<=1) return 1e18; int m=(l+r)/2; Real x=real(ps[m]); Real ret=min(rec(l,m),rec(m,r)); inplace_merge(begin(ps)+l,begin(ps)+m,begin(ps)+r,[&](Point a,Point b){ return imag(a) b; for(int i=l;i=ret) continue; for(int j=(int)b.size()-1;j>=0;j--){ if(abs(imag(ps[i]-b[j]))>=ret) break; ret=min(ret,abs(ps[i]-b[j])); } b.push_back(ps[i]); } return ret; }; return rec(0,(int)ps.size()); } // 凸多角形系統 // 凸多角形の頂点は反時計周りに訪れる順序 // v // 頂点は反時計周りに訪れる順序,時計回りとなるような3点があるとfalse bool is_convex(const vector &ps){ int n=(int)ps.size(); for(int i=0;i convex_hull(vector p){ int n=(int)p.size(),k=0; if(n<=2)return p; sort(begin(p),end(p),[](Point a,Point b){ return real(a)!=real(b)?real(a)ch(2*n); for(int i=0;i=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--; } for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){ // while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--; } ch.resize(k-1); return ch; } // // v 整数で凸法 // using P=pair; // vector

convex_hull(vector

p){ // int n=(int)p.size(),k=0; // if(n<=2)return p; // sort(begin(p),end(p)); // vector

ch(2*n); // auto crf=[&](P u,P v){return u.first*v.second-u.second*v.first;}; // auto dff=[&](P u,P v){return make_pair(u.first-v.first,u.second-v.second);}; // for(int i=0;i=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--; // // while(k>=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--; // } // for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){ // while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--; // // while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--; // } // ch.resize(k-1); // return ch; // } // 傾き,切片を返す // 傾きがバカデカくなるような時,知らん pair least_square_method(vector p){ Real xy=0,x=0,y=0,x_2=0; int n=(int)p.size(); for(int i=0;i<(int)p.size();i++){ xy+=p[i].real()*p[i].imag(); x+=p[i].real(); y+=p[i].imag(); x_2+=p[i].real()*p[i].real(); } Real a=(n*xy-x*y)/(n*x_2-x*x); Real b=(x_2*y-xy*x)/(n*x_2-x*x); return make_pair(a,b); } signed main(){ int n;cin>>n; vector v; rep(i,n){ int a;cin>>a; v.push_back(Point(i,a)); } auto [a,b]=least_square_method(v); Real x=b; Real cost=0; rep(i,n){ cost+=(v[i].imag()-x)*(v[i].imag()-x); x+=a; } cout<