#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
// precomp complexity: 1e6 log^3(1e6)
// /*
int buc[8] = {500000,250000,125000,62496,20832,3472,183,1};
int count(vector<int> &v, int x) {return upper_bound(v.begin(),v.end(),x)-lower_bound(v.begin(),v.end(),x);}
int rich(vector<int> v, int it) {
  int sz = v.size();
  if(sz==1) return v[0];
  int fst = sz/buc[it];
  int fCnt = buc[it] - (sz % buc[it]), sCnt = sz % buc[it];
  vector<int> a, b;
  int cur = 0;
  for(int i=0;i<fCnt;i++) {
    for(int j=0;j<fst;j++) for(int k=0;k<j;k++) a.push_back(v[j+cur]),b.push_back(v[k+cur]);
    cur += fst;
  }
  for(int i=0;i<sCnt;i++) {
    for(int j=0;j<=fst;j++) for(int k=0;k<j;k++) a.push_back(v[j+cur]),b.push_back(v[k+cur]);
    cur += fst + 1;
  }
  vector<int> c = ask(a,b);
  sort(c.begin(),c.end());
  vector<int> win;
  for(int i=0;i<fCnt*fst;i++) if(count(c,v[i])==fst-1) win.push_back(v[i]);
  for(int i=fCnt*fst;i<sz;i++) if(count(c,v[i])==fst) win.push_back(v[i]);
  return rich(win,it+1);
}
int richest(int N, int T, int S) {
  buc[0]=(N==1000?1:500000);
  vector<int> v(N);
  iota(v.begin(),v.end(),0);
  return rich(v,0);
}
// */

/*
using ll = long long;
pair<long long,int> dp[9][1000005];
long long c2(int n) {return 1LL*n*(n-1)/2;}
struct line{
	ll m, c;
	line(): m(0), c(1e18){}
	line(ll _m, ll _c): m(_m), c(_c){}
	ll operator()(int x){return m * x + c;}
	bool operator==(line y){return m == y.m && c == y.c;}
};
struct node{
	int s, e, m;
	line sth; int sid;
	node *l, *r;
	node(int _s, int _e): s(_s), e(_e), m(_s+_e>>1) {
    if(e-s!=1) {
      l = new node(s,m);
      r = new node(m,e);
    }
  }
	void up(int x, int y, line nl, int i) {
    if(x==s&&y==e) {
      bool lft = nl(s) < sth(s), mid = nl(m) < sth(m), rgt = nl(e) < sth(e);
      if(mid) swap(nl, sth), swap(i,sid);
      if(e - s == 1 || nl == line() || lft == rgt) return;
      if(lft != mid) (*l).up(s,m,nl,i);
      else (*r).up(m,e,nl,i);
      return;
    }
    if(y<=m) (*l).up(x,y,nl,i);
    else if(x>=m) (*r).up(x,y,nl,i);
    else (*l).up(x,m,nl,i),(*r).up(m,y,nl,i);
	}
	pair<ll,int> operator [](int x) {
		if(e - s == 1) return {sth(x),sid};
    if(l == nullptr) return {sth(x),sid};
		if(x < m) return min({sth(x),sid}, (*l)[x]);
		else return min({sth(x),sid}, (*r)[x]);
	}
  void purge() {
    sth = line();
    if(e-s!=1) (*l).purge(),(*r).purge();
  }
};
// dp[i-1][k] + (k - (j-km))(mc2) + (j-km)((m+1)c2)
// j((m+1)c2 - mc2) = jm
// so its jm + dp[i-1][k] + k(mc2) - km^2
node rt0(1,1000005), rt1(1,1000005);
main() {
  dp[0][1]={0,1};
  for(int i=1;i<=1000000;i++) rt0.up(i,i+1,line(i,-c2(i+1)),1);
  for(int i=2;i<1000005;i++) dp[0][i]={1000000000,1};
  for(int i=1;i<9;i++) {
    printf("doing %lld\n",i);
    (i&1?rt1:rt0).purge();
    for(int j=1;j<1000001;j++) {
      dp[i][j]=min((i&1?rt0:rt1)[j],{dp[i-1][j].first,1});
      for(int k=1;k<=(1000000/j);k++) {
        (i&1?rt1:rt0).up(k*j,min(1000001,(k+1)*j),line(k,dp[i][j].first+j*c2(k)-1LL*j*k*k),j);
      }
    }
  }
  cout << dp[8][1000000].first << "\n";
  for(int x=1000000,i=9;x>1;) {
    cout << "no parts "<<dp[--i][x].second << "\n";
    x = dp[i][x].second;
  }
}
// 1000000 (0)
// 500000 (500000)
// 250000 (750000)
// 125000 (875000)
// 62500 (937500)
// */