#include using namespace std; using Int = long long; //BEGIN CUT HERE namespace MonotoneMinima{ vector used; template void dfs(int l,int r,int a,int b,vector &dp,F dist){ if(l==r) return; int m=(l+r)>>1; int idx=a; T res=dp[idx+1]+dist(idx,m); for(int i=a;i void solve(int l,int r,vector &dp,F dist){ if(l+1==r){ if(!used[l]) dp[l]=dp[r]+dist(l,l),used[l]=1; else dp[l]=min(dp[l],dp[r]+dist(l,l)); return; } int m=(l+r)>>1; solve(m,r,dp,dist); dfs(l,m,m,r,dp,dist); solve(l,m,dp,dist); } // dist(i,l) + dist(j,k) >= dist(i,k) + dist(j,l) // if( i<=j && k<=l ) template T solve(int n,F dist){ vector dp(n+1,0); used.assign(n+1,0); used[n]=1; solve(0,n,dp,dist); return dp[0]; } }; //END CUT HERE //INSERT ABOVE HERE using ll = long long; signed YUKI_703(){ int n; cin>>n; vector as(n),xs(n),ys(n); for(int i=0;i>as[i]; for(int i=0;i>xs[i]; for(int i=0;i>ys[i]; auto dist= [&](int i,int j)->ll{ ll s=abs(as[i]-xs[j]); ll t=abs(ys[j]); return s*s+t*t; }; cout<(n,dist)<>n; vector as(n),xs(n),ys(n); for(int i=0;i>as[i]; for(int i=0;i>xs[i]; for(int i=0;i>ys[i]; auto dist= [&](int i,int j)->ll{ ll s=abs(as[i]-xs[j]); ll t=abs(ys[j]); return s+t; }; cout<(n,dist)<>n; vector as(n),xs(n),ys(n); for(int i=0;i>as[i]; for(int i=0;i>xs[i]; for(int i=0;i>ys[i]; auto dist= [&](int i,int j)->ll{ ll s=abs(as[i]-xs[j]); ll t=abs(ys[j]); return s*s*s+t*t*t; }; cout<(n,dist)<