/*
 * =====================================================================================================
 *  A400000_1T.c  --  the city-building sequence (OEIS A400000), computed quickly and exactly,
 *                    tuned for runs of up to about 10^12 (one trillion) terms
 * =====================================================================================================
 *
 *      a(n) = the least h >= 0 such that a building of height h at position n
 *             sees exactly h of the earlier buildings 1, ..., n-1.
 *
 *  One file, standard C (C11), no libraries beyond libc/libm.  Build with gcc or clang:
 *
 *      Linux (x86-64 or ARM):   cc -O3 -march=native -fno-math-errno -o A400000_1T A400000_1T.c -lm
 *      macOS (Apple silicon):   clang -O3 -mcpu=native -o A400000_1T A400000_1T.c
 *
 *  Examples:
 *
 *      ./A400000_1T -n 10000 -o b400000.txt        first 10^4 terms as an OEIS b-file (lines "n a(n)")
 *      ./A400000_1T -n 100 -f c                     first 100 terms as a comma-separated list, on stdout
 *      ./A400000_1T -n 1e12 -f none -S stats.txt    10^12 terms; keep only the statistics (no term output)
 *      ./A400000_1T -n 1e9 -s 999999001 -o end.txt  compute 10^9 terms, write only the last 1000
 *      ./A400000_1T -h                              all options
 *
 *  This comment explains the sequence (1), the basic method (2), the optimizations that make it fast (3),
 *  how the program checks itself (4), the options, output and resources (5), and where things are in the
 *  code (6).
 *
 *
 *  1. THE SEQUENCE
 *  ---------------
 *  Buildings go up one at a time along a street, building n at position n, and each new building gets the
 *  height a(n) defined above.  The rooftop of building i is seen from the point (n, h) if the straight
 *  segment from (i, a(i)) to (n, h) does not pass strictly below the rooftop of any building in between.
 *  A rooftop lying exactly on the segment does not block the view: collinear rooftops count as visible.
 *
 *      n    = 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 *      a(n) = 0  1  1  2  1  2  1  3  1  2  1  3  1  2  1 10  1  2  2  3  1  3  1  4
 *
 *  For example, a(4) = 2.  From height 1 at position 4 the rooftops of buildings 3 and 2 are visible
 *  (building 3's rooftop lies exactly on the segment from (2,1) to (4,1)): that is 2 buildings, not 1.
 *  From height 2 buildings 3 and 2 are visible but building 1 is hidden behind building 2: exactly 2.
 *
 *  Most terms are tiny (95% are <= 8), but now and then a much taller building appears.  The records
 *  include a(1246) = 111, a(888420938) = 1910, a(66490736512) = 1998 and a(147875405265) = 296961, which
 *  is the tallest building among the first 4.4*10^12.  After a record the city starts over: the terms that
 *  follow repeat the beginning of the sequence raised by one floor (after 296961, a(n+i) = a(i) + 1 for
 *  i = 1..2721).
 *
 *
 *  2. THEORY OF OPERATION: SIGHT LINES (R. Sigrist's method)
 *  ---------------------------------------------------------
 *  Instead of doing geometry, every earlier building i keeps one number, its horizon slope s(i): the
 *  steepest slope from its rooftop (i, a(i)) to the rooftop of any later building.  (Before there is a
 *  later building, s(i) = -a(i), the slope down to the ground next door, which hides nothing.)  All rooftops
 *  between i and n lie on or below the line through (i, a(i)) with slope s(i), and one of them lies on it.
 *  So building i is visible from (n, h) exactly when the point (n, h) is on or above that line:
 *
 *      i is visible from (n, h)  <=>  h >= a(i) + s(i)*(n - i)  <=>  h >= level_i(n),
 *
 *      level_i(n) = max(0, ceil(a(i) + s(i)*(n - i)))   = the lowest height at n from which i is seen.
 *
 *  Visibility is monotone in h (a taller viewer sees everything a shorter one sees), so the number of
 *  earlier buildings visible from (n, h) is just a count of levels,
 *
 *      v_n(h) = #{ i < n : level_i(n) <= h },
 *
 *  a nondecreasing function of h.  The difference v_n(h) - h starts at v_n(0) >= 0 and drops by at most 1
 *  each time h grows by 1, so the first h with v_n(h) <= h has v_n(h) = h exactly.  Therefore
 *
 *      a(n) = min{ h : v_n(h) <= h }        (and then v_n(a(n)) = a(n)).
 *
 *  Once a(n) is chosen, the new rooftop (n, a(n)) stands between every earlier building and every later
 *  position.  For each building i visible from (n, a(n)), the slope to the new rooftop,
 *  (a(n) - a(i)) / (n - i), is at least s(i); if it is steeper it becomes the new s(i): the sight line
 *  "pivots" through the new rooftop.  Hidden buildings are not affected (their line already passes above
 *  (n, a(n))).  Finally the new building starts with s(n) = -a(n).
 *
 *  In the code a sight line is (i, a, dv, dn): building i, its height a, and its slope s = dv/dn as an
 *  exact fraction with dn > 0.  Its level at step m is max(0, a + ceil(dv*(m - i)/dn)).  All arithmetic is
 *  exact integer arithmetic; nothing is rounded.
 *
 *  A rising line (dv > 0) only gets higher, and only a building of height >= its level could ever pivot
 *  it.  So a rising line whose level is above every height that will ever occur can never be seen again
 *  and is dropped.  The program uses a height cap HMAX = 2^19 - 1 = 524287 for this, enough for every
 *  n < 2^42.  If some a(n) ever exceeded HMAX the program would stop with an error rather than give a wrong
 *  answer.
 *
 *  Done directly, every live sight line (there are millions) is evaluated at every step: about 6
 *  microseconds per term, or two months for 10^12 terms.  This program gets the same answers in about
 *  1.6 nanoseconds per term on an Apple M2 Ultra (Mac Studio): under half an hour for 10^12 terms.
 *
 *
 *  3. THE OPTIMIZATIONS
 *  --------------------
 *  None of these changes any result.  Each one only skips work that cannot affect the answer.
 *
 *  (a) Tiers: look only at the lines that can matter.
 *      To decide that a(n) = h, only the levels <= h matter, and h is almost always small: 95% of the
 *      terms are <= 8, 99.6% are <= 24 and 99.92% are <= 64.  So the lines are filed by their current
 *      level:
 *
 *          T0      level <= 8 (K0)              about 10 lines; all of them are updated at every step
 *          F       falling lines above 8        a few dozen, sorted by the step at which they reach 8
 *          tier 1  rising lines, level (8, 24]
 *          tier 2  (24, 64]      tier 3  (64, 128]      tier 4  (128, 192]
 *          tier 5  (192, 768]    tier 6  (768, 4096]    tier 7  (4096, HMAX]   (the "top tier")
 *
 *      Every line with level <= 8 is in T0, so whenever v(h) <= h for some h <= 8 (about 95% of the
 *      steps) the step is decided by T0 alone: the "fast path".  Otherwise the "slow path" counts the
 *      levels of F and then of the tiers, one tier at a time going up, until it finds an h with
 *      v(h) <= h.  The tiers above that are not looked at.  Rising lines only go up, so a line filed in
 *      tier t never has to be counted below tier t's range.  Lines that have risen past their tier are
 *      moved up lazily, only when a tier has grown enough to be worth cleaning ("maintenance").
 *
 *  (b) No division on the fast path.
 *      T0 stores each line's height at the current position as Q + R/dn (0 <= R < dn) and its slope as
 *      qd + rd/dn.  Moving to the next position takes two additions and a comparison.  A falling line in
 *      F knows in advance the step D at which it comes down to level 8, and joins T0 then.
 *
 *  (c) Precomputed exits for the upper tiers.
 *      The top tier holds over a million slowly rising lines that will almost never be seen again.  When
 *      a line enters it, the step at which it will rise past HMAX (its "expiry") is computed once.
 *      Maintenance just drops expired lines and never evaluates a level there.  Tiers 5 and 6 likewise
 *      store the step at which each line will leave them, so maintaining them needs no division either.
 *
 *  (d) Memoized runs: the city repeats itself.
 *      Right after a building taller than B, every line with level <= B was visible from the tall rooftop
 *      and has just pivoted through it.  The run of terms <= B that follows depends only on a small
 *      "key": the T0 lines, plus the few falling lines that come down to <= B within a window of W steps,
 *      all written relative to the start of the run.  Every other line stays above B during the run and
 *      cannot affect it.  Runs with the same key recur constantly.  So each distinct run is computed once
 *      and stored in a hash table, with its terms and the sight lines it leaves behind (already sorted
 *      into T0, F and the tiers).  When the key comes back the whole run is replayed: its terms are
 *      emitted and its lines are put in place, with no step-by-step work.
 *
 *      There are two memo levels: B1 = 64 with window W1 = 4096, and B2 = 192 with W2 = 65536.  A new
 *      level-1 run is computed with a plain list of its key lines.  A new level-2 run is computed by
 *      running the engine itself on just its key lines, with level-1 replays inside it.  A stored run is
 *      used only if no falling line outside its key comes down to <= B before the run ends.  Otherwise
 *      the steps are computed normally.  In practice about 99.9% of the level-2 lookups hit, a hit
 *      replays about 16,000 terms, and about 99.99% of all terms come from replays.
 *
 *  (e) Replays update the statistics in constant time.
 *      Each stored run carries its sum, its maximum, and the count and first offset of each height.  The
 *      64-bit FNV-1a hash of all terms (used to compare runs) also advances in O(1).  For a term x < 256,
 *      (h XOR x) * P = (h + d) * P where d depends only on the low byte of h, and the low byte of the
 *      result depends only on the low byte of h.  So over a run of L terms, h -> h * P^L + C[h mod 256].
 *      The 256 possible constants C are filled in lazily, only for the low bytes that actually occur.
 *      (When terms are written out, the replayed terms are formatted one by one.)
 *
 *  (f) Lazy blocks and bounded memory.
 *      A level-2 run leaves thousands of short-lived lines in the top tier, and usually they expire
 *      before any search reaches the top tier.  So they stay inside the stored run as a "block", copied
 *      out only if a search actually gets that high.  Stored runs are allocated at their exact size and
 *      their bytes are counted.  When a level's table exceeds its budget (option -M), the least-used
 *      entries are evicted.  Use counts are halved at each eviction, so recent use counts most.
 *
 *  (g) Exact 64-bit arithmetic.
 *      Heights are below 2^20 and positions below 2^43 (n < 2^42, plus the length of a simulated run), so
 *      every product such as dv*(m - i) is below 2^63, and all arithmetic is plain exact 64-bit integer
 *      arithmetic.  64-bit division is slow on x86, so there floor(x/dn) is estimated with a
 *      floating-point reciprocal and corrected exactly with one multiplication and comparison.  On ARM
 *      (Apple silicon) the hardware division is fast and is used directly (LEVEL_INT below).
 *
 *
 *  4. CHECKS
 *  ---------
 *  * Option -t T (default 10000): the first T terms are also computed straight from the definition, with
 *    no sight lines, tiers or memo.  For each candidate height, the program walks back along the street
 *    and counts the visible rooftops.  The results are compared with the fast engine.  Replays begin at
 *    n = 1247 (level 1) and n = 61899 (level 2), so -t 100000 also exercises both memo levels (that takes
 *    about 10 seconds).
 *  * The program carries reference values (sum, maximum and FNV-1a hash of a(1..n)) from the computation
 *    behind the published b-files, which was itself checked by an independent memo-free recomputation.
 *    Whenever a run passes one of those n, the values are compared, and the program stops at once if they
 *    differ.
 *  * Option -m 0 switches the memo off.  The terms are then computed step by step by the tiered engine
 *    alone.  That is a different path (much slower) that must give the same hash.
 *  * The engine checks its own invariant v(h) = h at every slow step and in every simulated run.
 *
 *
 *  5. OPTIONS, OUTPUT AND RESOURCES
 *  --------------------------------
 *      -n N        compute a(1..N); default 10000.  N may be written 1000000, 1e12 or 2^40.  N < 2^42.
 *      -o FILE     write the terms to FILE (default: standard output)
 *      -f FORMAT   b     b-file: one line "n a(n)" per term (the default)
 *                  c     comma-separated list "a(1), a(2), ..." on one line
 *                  none  no terms are written (progress, statistics and checks only)
 *      -s START    write only a(START..N); everything is still computed from n = 1
 *      -S FILE     at the end, write statistics to FILE: the records (A399949, A399950) and, for every
 *                  height that occurs, its first index (A399763) and its number of occurrences
 *      -p SEC      progress report on stderr at most every SEC seconds (default 10; 0 = at every 2^30
 *                  terms).  Each report has n, speed, ETA, and the sum and hash of a(1..n).
 *      -q          quiet: nothing on stderr except errors
 *      -t T        check a(1..T) against the direct computation (default 10000; 0 = no check)
 *      -m L        memo levels: 2 (default), 1 or 0
 *      -M GB       memory budget for the memo tables, in GiB (default 8)
 *
 *  With -f none and the default memory budget, 2^40 = 1.1*10^12 terms took 29 minutes (1.59 ns per term)
 *  and 11-12 GB of memory on an Apple M2 Ultra; the time per term is about the same over the whole range.
 *  A heavily loaded Intel Xeon 8268 server ran at about 8-9 ns per term.  Writing the terms costs far
 *  more than computing them.  A b-file of the first 10^9 terms is about 12 GB and of 10^12 terms about
 *  15 TB; the comma list is about 3 bytes per term (3.0 GB for 10^9 terms).  Output can be piped, e.g.
 *  ./A400000_1T -n 1e9 | gzip > b400000.txt.gz
 *
 *  Exit status: 0 = done, 1 = a check failed or bad options, 2 = error (out of memory, height cap,
 *  output error).
 *
 *
 *  6. MAP OF THE CODE
 *  ------------------
 *      configuration, types ...... compile-time parameters; the sight-line structs
 *      exact arithmetic .......... floor/ceil division, levels, slope comparison
 *      engine state and filing ... T0, F, the tiers: where a line goes and when it moves
 *      one step .................. step() (fast path) and slow_path()
 *      memo ...................... keys, stored runs, the two simulators, the hash table, replay
 *      statistics and output ..... sums, counts, records, hash; b-file / comma formatting
 *      checks .................... the direct computation; reference values
 *      main ...................... options, the main loop, reports
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <math.h>

typedef int64_t i64;
typedef uint64_t u64;

#if defined(__GNUC__) || defined(__clang__)
#define NORETURN __attribute__((noreturn))
#else
#define NORETURN
#endif

/* =====================================================================================================
 *  CONFIGURATION
 *  These are the values used for the reference computation, except HMAX (see below).  HMAX and LEVEL_INT
 *  can be changed with -D on the compiler command line.  The others are best left alone (the memo needs
 *  B1 and B2 to be tier bounds, and B2 < 256).
 * ===================================================================================================== */

/* Height cap.  Rising sight lines above HMAX are dropped, since they could only matter for a building
 * taller than HMAX, and the program stops with an error if some a(n) would exceed HMAX.  The tallest term
 * below n = 2^42 is 296961, so 2^19 - 1 = 524287 is never reached in the range this program allows, and a
 * lower cap is faster: rising lines are dropped sooner (12% faster to 2^40 than with 2^20 - 1, the cap of
 * the reference computation, which went far beyond 2^42).  The 64-bit bounds of the arithmetic
 * need HMAX < 2^20. */
#ifndef HMAX
#define HMAX 524287
#endif
#if HMAX >= (1 << 20) || HMAX <= 4096
#error "HMAX must be between 4097 and 2^20 - 1"
#endif

/* N must be below NLIMIT.  Positions then stay below NLIMIT + LMAX2 + 2 < 2^43, so with |dv|, |a| < 2^20
 * every product of the form dv*(m - i) or (a - K)*dn is below 2^63 and nothing can overflow. */
#define NLIMIT (1LL << 42)

/* How a level is evaluated: 1 = hardware integer division, 0 = floating-point reciprocal plus an exact
 * correction.  64-bit division is fast on ARM and slow on most x86 processors. */
#ifndef LEVEL_INT
#if defined(__aarch64__) || defined(__arm64__) || defined(_M_ARM64)
#define LEVEL_INT 1
#else
#define LEVEL_INT 0
#endif
#endif

#define K0 8                       /* tier 0 holds every line with level <= K0 */
#define NT 7                       /* number of tiers above tier 0 */
static const i64 KT[NT + 1] = {K0, 24, 64, 128, 192, 768, 4096, HMAX};   /* tier t: levels (KT[t-1], KT[t]] */
#define T_MID 5                    /* tier (192, 768]:  exit and expiry steps precomputed when a line enters */
#define T_UP 6                     /* tier (768, 4096]: exit and expiry steps precomputed */
#define T_TOP 7                    /* tier (4096, HMAX]: expiry steps precomputed, levels never re-evaluated */
#define MAINT_MUL 16               /* a tier is maintained when it holds more than MAINT_MUL * (its size after */
#define MAINT_ADD 262144           /*   its last maintenance) + MAINT_ADD lines; checked every 256 steps      */
#define B1 64                      /* memo level 1: runs of terms <= B1 that follow a term > B1, keyed by T0  */
#define W1 4096                    /*   and the falling lines that reach level <= B1 within W1 steps          */
#define B2 192                     /* memo level 2: the same with B2 and W2.  B2 < 256 because the terms of a */
#define W2 65536                   /*   stored run are kept in one byte each                                  */
#define LMAX1 (1LL << 20)          /* longest run stored at level 1 */
#define LMAX2 (1LL << 24)          /* longest run stored at level 2 */
#define BLK_HORIZON (1LL << 22)    /* top-tier lines of a level-2 run that expire within this many steps stay in a lazy block */
#define REPORT_EVERY (1LL << 30)   /* the statistics are made exact at every multiple of 2^30 (progress, reference checks) */
#define FNV_OFFSET 0xcbf29ce484222325ULL       /* 64-bit FNV-1a: hash = (hash ^ term) * FNV_PRIME for each term */
#define FNV_PRIME 0x100000001b3ULL
static const i64 LB[3] = {0, B1, B2}, LW[3] = {0, W1, W2}, LMAX[3] = {0, LMAX1, LMAX2};

/* =====================================================================================================
 *  TYPES
 * ===================================================================================================== */

/* A sight line: the line through the rooftop (i, a) of building i with slope dv/dn, dn > 0.  Its level at
 * step m is max(0, a + ceil(dv*(m - i)/dn)).  inv = 1.0/dn is kept for the floating-point division. */
typedef struct { i64 i, dn; int32_t a, dv; double inv; } Line;

/* A line in tier 0, kept incrementally: its height at the current step is Q + R/dn with 0 <= R < dn, and
 * each step adds the slope dv/dn = qd + rd/dn (qd = floor(dv/dn), 0 <= rd < dn).  Its level is
 * max(0, Q + (R != 0)). */
typedef struct { i64 Q, R, qd, rd, dn, i; int32_t a, dv; } L0;

/* A falling line with level above K0, and D = the first step at which its level is <= K0. */
typedef struct { Line l; i64 D; } FL;

typedef struct { Line *v; i64 n, cap; } Vec;     /* a growable array of lines (one tier) */
typedef struct { Line l; i64 lev; } Pend;        /* a line waiting to be re-filed at the end of a slow step */
typedef struct { i64 i, a, dv, dn; } PL;         /* a plain line, without the extra fields */

/* =====================================================================================================
 *  SMALL UTILITIES
 * ===================================================================================================== */

/* Print an error and stop (exit status 2).  n > 0 says where in the sequence it happened. */
NORETURN static void die(const char *msg, i64 n) {
    if (n > 0) fprintf(stderr, "A400000_1T: error: %s (at n = %lld)\n", msg, (long long)n);
    else fprintf(stderr, "A400000_1T: error: %s\n", msg);
    exit(2);
}
/* realloc / calloc that never return NULL (and never ask for 0 bytes). */
static void *xrealloc(void *p, size_t s) { p = realloc(p, s ? s : 1); if (!p) die("out of memory", 0); return p; }
static void *xcalloc(size_t k, size_t s) { void *p = calloc(k ? k : 1, s ? s : 1); if (!p) die("out of memory", 0); return p; }
/* Wall-clock time in seconds. */
static double now(void) { struct timespec ts; timespec_get(&ts, TIME_UTC); return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec; }
/* Index of the lowest set bit of m (m != 0). */
static inline int lowest_bit(uint32_t m) {
#if defined(__GNUC__) || defined(__clang__)
    return __builtin_ctz(m);
#else
    int k = 0; while (!(m & 1)) { m >>= 1; k++; } return k;
#endif
}

/* =====================================================================================================
 *  EXACT ARITHMETIC
 *  All quantities are exact integers.  The bounds (|a|, |dv| < 2^20, positions < 2^43) keep every product
 *  below 2^63, so no wider arithmetic is ever needed.
 * ===================================================================================================== */

/* floor(x/y) and ceil(x/y) for y > 0.  C division truncates toward zero; the remainder fixes it up. */
static inline i64 floordiv(i64 x, i64 y) { i64 q = x / y; return q - ((x % y) < 0); }
static inline i64 ceildiv(i64 x, i64 y) { i64 q = x / y; return q + ((x % y) > 0); }

/* The same from a floating-point estimate: r = round(x * (1/dn)) is within 1 of x/dn while |x/dn| < 2^50,
 * and one exact comparison of x with r*dn then gives the exact floor or ceiling.  (Beyond 2^50 only levels
 * far above HMAX are involved, where being off by a few units cannot matter.) */
static inline i64 floordiv_fp(i64 x, i64 dn, double inv) { i64 r = llrint((double)x * inv); return r - (x - r * dn < 0); }
#if !LEVEL_INT
static inline i64 ceildiv_fp(i64 x, i64 dn, double inv) { i64 r = llrint((double)x * inv); return r + (x - r * dn > 0); }
#endif

/* Level of line l at step m: the lowest height at position m from which building l->i is visible. */
static inline i64 level_at(const Line *l, i64 m) {
#if LEVEL_INT
    i64 v = l->a + ceildiv((i64)l->dv * (m - l->i), l->dn);
#else
    i64 v = l->a + ceildiv_fp((i64)l->dv * (m - l->i), l->dn, l->inv);
#endif
    return v < 0 ? 0 : v;
}
/* The same for a line given by its four numbers, always with exact integer division. */
static inline i64 level_plain(i64 i, i64 a, i64 dv, i64 dn, i64 m) {
    i64 v = a + ceildiv(dv * (m - i), dn);
    return v < 0 ? 0 : v;
}
static inline Line mkline(i64 i, i64 a, i64 dv, i64 dn) { return (Line){i, dn, (int32_t)a, (int32_t)dv, 1.0 / (double)dn}; }
/* Is slope dv1/dn1 steeper than dv0/dn0?  (Both denominators are positive.) */
static inline int steeper(i64 dv1, i64 dn1, i64 dv0, i64 dn0) { return dv1 * dn0 > dv0 * dn1; }
/* Histogram bucket of a level: levels above HMAX all share bucket HMAX + 1. */
static inline i64 hbucket(i64 v) { return v <= HMAX ? v : HMAX + 1; }

/* =====================================================================================================
 *  ENGINE STATE
 *
 *  Every live sight line is in exactly one of these places:
 *    T0       lines with level <= K0, kept incrementally (L0); levs[] holds their levels at the step being
 *             computed.  Right after a step T0 may briefly hold a line that has risen above K0; the next
 *             step moves it out.
 *    F        falling lines (dv < 0) with level > K0, sorted by D, the step at which they reach K0
 *    tier t   rising or flat lines (dv >= 0) whose level was in (KT[t-1], KT[t]] when they were filed
 *             (t = 1..NT).  A line may have risen past KT[t] since then; it moves up at the next
 *             maintenance.  It is never below KT[t-1], because rising lines only rise, and a line's slope
 *             can only change when it is visible, which needs a slow step that reaches its tier.
 *    blocks   short-lived top-tier lines still inside a stored run (see the memo section)
 *  Rising lines above HMAX are not kept anywhere.
 * ===================================================================================================== */
static L0 *T0; static i64 t0n, t0cap;        /* tier 0 */
static i64 *levs;                            /* levels of the T0 lines at the current step */
static Vec tier[NT + 1];                     /* tiers 1..NT */
static i64 maint[NT + 1];                    /* tier t is maintained once it holds more than maint[t] lines */
static FL *F; static i64 fn, fcap;           /* falling lines above K0, sorted by D */
static i64 *flev;                            /* scratch: the levels of the F lines during a slow step */
static i64 nextmaint;                        /* the tiers are checked for maintenance after this step */
static i64 *top_exp, top_expcap;             /* top tier: expiry step of each line (after it, level > HMAX) */
static i64 *up_exit, *up_exp, up_cap;        /* tier T_UP: last step with level <= KT[T_UP], and expiry */
static i64 *mid_exit, *mid_exp, mid_cap;     /* tier T_MID: the same two numbers, used when a line moves up */
struct Entry;
typedef struct { struct Entry *E; i64 e, exp; } Block;   /* the short-lived top-tier lines of a run replayed at e */
static Block *blk; static i64 nblk, blkcap;  /* pending blocks */
static int use_blocks;                       /* blocks are used by the main engine only */
static void blocks_materialize(void);
static void blocks_expire(i64 m);

/* Scratch space shared by the main engine and the private one of simulate2(); always clean between steps. */
static i64 *tlev[NT + 1], tlevcap[NT + 1];   /* levels of a tier's lines during a slow step */
static i64 *levhist;                         /* histogram of levels 0..HMAX+1 during a slow step */
static Pend *pend; static i64 pendn, pendcap;            /* lines to re-file at the end of a slow step */
typedef struct { Line l; i64 lev, te, tp; } MidOut;     /* a T_MID line leaving its tier during a slow step */
static MidOut *midout; static i64 nmidout, midoutcap;
static i64 nslow;                            /* number of slow steps (statistics) */

/* simulate2() computes a new level-2 run by running a second, private engine on the lines of its key.
 * These functions swap the complete engine state out and back in. */
typedef struct {
    L0 *T0; i64 t0n, t0cap; i64 *levs; Vec tier[NT + 1]; i64 maint[NT + 1]; FL *F; i64 fn, fcap; i64 *flev;
    i64 nextmaint; i64 *top_exp, top_expcap; Block *blk; i64 nblk, blkcap; int use_blocks;
    i64 *up_exit, *up_exp, up_cap; i64 *mid_exit, *mid_exp, mid_cap;
} Eng;
static void eng_save(Eng *e) {
    e->T0 = T0; e->t0n = t0n; e->t0cap = t0cap; e->levs = levs;
    for (int t = 0; t <= NT; t++) { e->tier[t] = tier[t]; e->maint[t] = maint[t]; }
    e->F = F; e->fn = fn; e->fcap = fcap; e->flev = flev; e->nextmaint = nextmaint;
    e->top_exp = top_exp; e->top_expcap = top_expcap; e->blk = blk; e->nblk = nblk; e->blkcap = blkcap; e->use_blocks = use_blocks;
    e->up_exit = up_exit; e->up_exp = up_exp; e->up_cap = up_cap; e->mid_exit = mid_exit; e->mid_exp = mid_exp; e->mid_cap = mid_cap;
}
static void eng_load(const Eng *e) {
    T0 = e->T0; t0n = e->t0n; t0cap = e->t0cap; levs = e->levs;
    for (int t = 0; t <= NT; t++) { tier[t] = e->tier[t]; maint[t] = e->maint[t]; }
    F = e->F; fn = e->fn; fcap = e->fcap; flev = e->flev; nextmaint = e->nextmaint;
    top_exp = e->top_exp; top_expcap = e->top_expcap; blk = e->blk; nblk = e->nblk; blkcap = e->blkcap; use_blocks = e->use_blocks;
    up_exit = e->up_exit; up_exp = e->up_exp; up_cap = e->up_cap; mid_exit = e->mid_exit; mid_exp = e->mid_exp; mid_cap = e->mid_cap;
}
/* An empty engine whose next step is m. */
static void eng_clear(i64 m) {
    T0 = NULL; t0n = t0cap = 0; levs = NULL;
    for (int t = 0; t <= NT; t++) { tier[t] = (Vec){0}; maint[t] = MAINT_ADD; }
    F = NULL; fn = fcap = 0; flev = NULL; nextmaint = m; top_exp = NULL; top_expcap = 0;
    blk = NULL; nblk = blkcap = 0; use_blocks = 0;
    up_exit = up_exp = NULL; up_cap = 0; mid_exit = mid_exp = NULL; mid_cap = 0;
}
/* Free the arrays of the current engine (the private one, when simulate2() is done with it). */
static void eng_free(void) {
    free(T0); free(levs); free(F); free(flev); free(top_exp); free(blk); free(up_exit); free(up_exp); free(mid_exit); free(mid_exp);
    for (int t = 0; t <= NT; t++) free(tier[t].v);
}

/* =====================================================================================================
 *  FILING: WHERE A LINE GOES
 * ===================================================================================================== */

/* Append a line to a tier array. */
static void vpush(Vec *a, Line l) {
    if (a->n == a->cap) { a->cap = a->cap ? 2 * a->cap : 1024; a->v = xrealloc(a->v, (size_t)a->cap * sizeof(Line)); }
    a->v[a->n++] = l;
}
/* Queue a line to be re-filed at the end of a slow step.  lev >= 0: its level (known); -1: it has just
 * pivoted and its level at the next step is computed then. */
static void ppush(Line l, i64 lev) {
    if (pendn == pendcap) { pendcap = pendcap ? 2 * pendcap : 1024; pend = xrealloc(pend, (size_t)pendcap * sizeof(Pend)); }
    pend[pendn++] = (Pend){l, lev};
}

#define EXPMAX (1LL << 61)   /* "never expires"; leaves room to add a step number without overflow */

/* Expiry of a line in the top tier: a step after which its level is certainly above HMAX.  For a rising
 * line, level(m) > HMAX as soon as dv*(m - i)/dn > HMAX - a, that is m - i > (HMAX - a)*dn/dv.  The
 * floating-point value is within a step of the truth wherever it matters (steps below 2^44), and "+ 2"
 * makes it a safe over-estimate: a line is only ever kept a little too long, never dropped too early.
 * Flat and falling lines never expire. */
static inline i64 top_expiry(const Line *l) {
    if (l->dv <= 0) return EXPMAX;
    double t = (double)(HMAX - l->a) * (double)l->dn / (double)l->dv;
    return t > (double)EXPMAX ? EXPMAX : l->i + (i64)t + 2;
}
/* Exact last step at which a rising line still has level <= KT[T_UP] = 4096:
 * a + ceil(dv*(m - i)/dn) <= K  <=>  dv*(m - i)/dn <= K - a  <=>  m <= i + floor((K - a)*dn/dv). */
static inline i64 up_exit_step(const Line *l) {
    if (l->dv <= 0) return EXPMAX;
    return l->i + floordiv((i64)(KT[T_UP] - l->a) * l->dn, l->dv);
}
/* File a line in the top tier with its expiry step. */
static void top_push(Line l, i64 expiry) {
    Vec *a = &tier[T_TOP];
    if (a->n == a->cap) { a->cap = a->cap ? 2 * a->cap : 1024; a->v = xrealloc(a->v, (size_t)a->cap * sizeof(Line)); }
    if (top_expcap < a->cap) { top_expcap = a->cap; top_exp = xrealloc(top_exp, (size_t)top_expcap * sizeof(i64)); }
    top_exp[a->n] = expiry; a->v[a->n++] = l;
}
/* File a line in tier T_UP with its exit step te and expiry tp. */
static void up_push(Line l, i64 te, i64 tp) {
    Vec *a = &tier[T_UP];
    if (a->n == a->cap) { a->cap = a->cap ? 2 * a->cap : 1024; a->v = xrealloc(a->v, (size_t)a->cap * sizeof(Line)); }
    if (up_cap < a->cap) { up_cap = a->cap; up_exit = xrealloc(up_exit, (size_t)up_cap * sizeof(i64)); up_exp = xrealloc(up_exp, (size_t)up_cap * sizeof(i64)); }
    up_exit[a->n] = te; up_exp[a->n] = tp; a->v[a->n++] = l;
}
/* File a line in tier T_MID, with the exit step from T_UP and the expiry it will need later. */
static void mid_push(Line l, i64 te, i64 tp) {
    Vec *a = &tier[T_MID];
    if (a->n == a->cap) { a->cap = a->cap ? 2 * a->cap : 1024; a->v = xrealloc(a->v, (size_t)a->cap * sizeof(Line)); }
    if (mid_cap < a->cap) { mid_cap = a->cap; mid_exit = xrealloc(mid_exit, (size_t)mid_cap * sizeof(i64)); mid_exp = xrealloc(mid_exp, (size_t)mid_cap * sizeof(i64)); }
    mid_exit[a->n] = te; mid_exp[a->n] = tp; a->v[a->n++] = l;
}
/* File a rising line in tier t, computing the extra numbers the upper tiers keep. */
static inline void tier_push(int t, Line l) {
    if (t == T_TOP) top_push(l, top_expiry(&l));
    else if (t == T_UP) up_push(l, up_exit_step(&l), top_expiry(&l));
    else if (t == T_MID) mid_push(l, up_exit_step(&l), top_expiry(&l));
    else vpush(&tier[t], l);
}
/* A line leaves tier T_MID with level lev at step m.  It goes to T_UP if lev <= 4096, else to the top tier
 * if it has not expired yet, else nowhere.  Its exit and expiry steps were computed when it entered T_MID. */
static inline void mid_leave(Line l, i64 lev, i64 te, i64 tp, i64 m) {
    if (lev <= KT[T_UP]) up_push(l, te, tp);
    else if (tp >= m) top_push(l, tp);
}

/* tier_of(lev): the tier 1..NT for a rising line with level lev > K0, or 0 if lev > HMAX (the line is
 * dropped).  Levels up to 4096 are looked up in a table. */
#define TTAB 4097
static unsigned char ttab[TTAB];
static int tier_of(i64 lev) {
    if (lev < TTAB) return ttab[lev];
    for (int t = 1; t <= NT; t++) if (lev <= KT[t]) return t;
    return 0;
}
static void build_ttab(void) {
    for (i64 v = 0; v < TTAB; v++) {
        int r = 0;
        for (int t = 1; t <= NT; t++) if (v <= KT[t]) { r = t; break; }
        ttab[v] = (unsigned char)r;
    }
}

/* Grow T0 and its level array together. */
static void t0_grow(void) {
    t0cap = t0cap ? 2 * t0cap : 256;
    T0 = xrealloc(T0, (size_t)t0cap * sizeof(L0)); levs = xrealloc(levs, (size_t)t0cap * sizeof(i64));
}
/* Add a line to T0, set up for step m: its height there is a + dv*(m - i)/dn = Q + R/dn with
 * Q = a + floor(dv*(m - i)/dn) and 0 <= R < dn; its slope is qd + rd/dn. */
static void t0_add(Line l, i64 m) {
    if (t0n == t0cap) t0_grow();
    i64 qd = floordiv(l.dv, l.dn);
    i64 x = (i64)l.dv * (m - l.i), q = floordiv_fp(x, l.dn, l.inv), r = x - q * l.dn;
    T0[t0n++] = (L0){l.a + q, r, qd, l.dv - qd * l.dn, l.dn, l.i, l.a, l.dv};
}
static Line l0_line(const L0 *l) { return mkline(l->i, l->a, l->dv, l->dn); }
/* Insert a falling line into F, keeping F sorted by D (F is short: a few dozen lines). */
static void f_insert(Line l, i64 D) {
    if (fn == fcap) { fcap = fcap ? 2 * fcap : 64; F = xrealloc(F, (size_t)fcap * sizeof(FL)); flev = xrealloc(flev, (size_t)fcap * sizeof(i64)); }
    i64 k = fn++;
    while (k > 0 && F[k - 1].D > D) { F[k] = F[k - 1]; k--; }
    F[k] = (FL){l, D};
}
/* A falling line with level above K0 joins F.  Its level reaches K0 at the first step m with
 * dv*(m - i)/dn <= K0 - a, that is m >= i + ceil((a - K0)*dn/(-dv)). */
static void f_add(Line l) { f_insert(l, l.i + ceildiv((i64)(l.a - K0) * l.dn, -(i64)l.dv)); }
/* File a line for step m, given its level lev at step m. */
static void place(Line l, i64 lev, i64 m) {
    if (lev <= K0) t0_add(l, m);
    else if (l.dv < 0) f_add(l);
    else { int t = tier_of(lev); if (t) tier_push(t, l); }      /* t == 0: a rising line above HMAX, dropped */
}

/* Maintenance of tier t at step m: lines that have risen past the tier move up (or are dropped once they
 * are above HMAX), and the tier's next threshold is set.  Lines are only ever moved up, to a different
 * tier, so the compaction of this tier is never disturbed. */
static void maintain(int t, i64 m) {
    Vec *a = &tier[t]; i64 w = 0;
    if (t == T_MID) {                     /* evaluate; a line that leaves needs no division to be filed */
        for (i64 k = 0; k < a->n; k++) {
            i64 lev = level_at(&a->v[k], m);
            if (lev > KT[t]) mid_leave(a->v[k], lev, mid_exit[k], mid_exp[k], m);
            else { a->v[w] = a->v[k]; mid_exit[w] = mid_exit[k]; mid_exp[w] = mid_exp[k]; w++; }
        }
        a->n = w;
        maint[t] = MAINT_MUL * w + MAINT_ADD;
        return;
    }
    if (t == T_UP) {                      /* the exit steps are known: no evaluation at all */
        for (i64 k = 0; k < a->n; k++) {
            if (up_exit[k] >= m) { a->v[w] = a->v[k]; up_exit[w] = up_exit[k]; up_exp[w] = up_exp[k]; w++; }
            else if (up_exp[k] >= m) top_push(a->v[k], up_exp[k]);
        }
        a->n = w;
        maint[t] = MAINT_MUL * w + MAINT_ADD;
        return;
    }
    if (t == T_TOP) {                     /* drop the expired lines and blocks */
        blocks_expire(m);
        for (i64 k = 0; k < a->n; k++) if (top_exp[k] >= m) { a->v[w] = a->v[k]; top_exp[w] = top_exp[k]; w++; }
        a->n = w;
        maint[t] = 2 * w + 4 * MAINT_ADD;
        return;
    }
    for (i64 k = 0; k < a->n; k++) {      /* tiers 1..4: evaluate and move up what has risen */
        i64 lev = level_at(&a->v[k], m);
        if (lev > KT[t]) { int t2 = tier_of(lev); if (t2) tier_push(t2, a->v[k]); }
        else a->v[w++] = a->v[k];
    }
    a->n = w;
    maint[t] = MAINT_MUL * w + MAINT_ADD;
}

/* =====================================================================================================
 *  ONE STEP
 * ===================================================================================================== */

/* The slow path of step n: no h <= K0 works, so the search continues upward through F and the tiers.
 * On entry the T0 levels for step n are in levs[] (and the T0 lines are already advanced to n + 1).
 * Returns a(n), with every line re-filed for step n + 1.
 * If bound > 0 and no h <= bound works, returns -1 having changed nothing except the T0 advance.  That is
 * how simulate2() finds the end of a level-2 run (a step taller than B2). */
static i64 slow_path(i64 n, i64 bound) {
    nslow++;
    /* 1. Histogram of the levels that could be <= the answer: T0 and F first ... */
    for (i64 k = 0; k < t0n; k++) levhist[hbucket(levs[k])]++;
    for (i64 k = 0; k < fn; k++) { flev[k] = level_at(&F[k].l, n); levhist[hbucket(flev[k])]++; }
    i64 c = 0, h = -1;
    for (i64 j = 0; j <= K0; j++) c += levhist[j];          /* c = v_n(K0) (we already know v_n(j) > j for j <= K0) */
    /* ... then one tier at a time.  When tier t is added, every line with level <= KT[t] has been counted
     * (lines in higher tiers have levels > KT[t]), so c = v_n(j) is exact for j up to KT[t]. */
    int tmax = 0; i64 tstart[NT + 1];
    for (int t = 1; t <= NT && h < 0 && !(bound > 0 && KT[t - 1] >= bound); t++) {
        if (t == T_TOP && nblk) blocks_materialize();       /* the lazy blocks are needed now */
        Vec *a = &tier[t];
        tstart[t] = a->n;
        if (tlevcap[t] < a->n) { tlevcap[t] = 2 * a->n; tlev[t] = xrealloc(tlev[t], (size_t)tlevcap[t] * sizeof(i64)); }
        for (i64 k = 0; k < a->n; k++) { i64 v = level_at(&a->v[k], n); tlev[t][k] = v; levhist[hbucket(v)]++; }
        tmax = t;
        for (i64 j = KT[t - 1] + 1; j <= KT[t]; j++) { c += levhist[j]; if (c <= j) { h = j; break; } }
    }
    /* 2. Clean the histogram (only the buckets that were touched). */
    for (i64 k = 0; k < t0n; k++) levhist[hbucket(levs[k])] = 0;
    for (i64 k = 0; k < fn; k++) levhist[hbucket(flev[k])] = 0;
    for (int t = 1; t <= tmax; t++) for (i64 k = 0; k < tstart[t]; k++) levhist[hbucket(tlev[t][k])] = 0;
    if (h < 0) {
        if (bound > 0) return -1;
        die("a term exceeds the height cap HMAX; recompile with a larger -DHMAX (at most 2^20 - 1)", n);
    }
    if (c != h) die("internal error: v(h) != h", n);

    /* 3. Pivot every visible line that passes strictly below (n, h), and collect the lines that must be
     *    re-filed: pivoted lines, T0 lines that have risen above K0, and tier lines that have outgrown
     *    their tier.  Re-filing waits until the end, so that no array is appended to while it is being
     *    compacted. */
    pendn = 0;
    for (i64 k = 0; k < t0n;) {
        L0 *l = &T0[k]; i64 lev = levs[k];
        if (lev <= h) {
            i64 ndv = h - l->a, ndn = n - l->i;
            if (steeper(ndv, ndn, l->dv, l->dn)) {          /* pivot through (n, h) */
                ppush(mkline(l->i, l->a, ndv, ndn), -1);
                T0[k] = T0[--t0n]; levs[k] = levs[t0n];
                continue;
            }
        } else if (lev > K0) {                              /* rose above K0: leaves T0 */
            ppush(l0_line(l), lev);
            T0[k] = T0[--t0n]; levs[k] = levs[t0n];
            continue;
        }
        k++;
    }
    {   i64 w = 0;
        for (i64 k = 0; k < fn; k++) {
            Line *l = &F[k].l;
            if (flev[k] <= h) {
                i64 ndv = h - l->a, ndn = n - l->i;
                if (steeper(ndv, ndn, l->dv, l->dn)) { ppush(mkline(l->i, l->a, ndv, ndn), -1); continue; }
            }
            F[w++] = F[k];
        }
        fn = w; }
    for (int t = 1; t <= tmax; t++) {
        Vec *a = &tier[t]; i64 w = 0;
        for (i64 k = 0; k < tstart[t]; k++) {
            Line l = a->v[k]; i64 lev = tlev[t][k];
            if (lev <= h) {
                i64 ndv = h - l.a, ndn = n - l.i;
                if (steeper(ndv, ndn, l.dv, l.dn)) { ppush(mkline(l.i, l.a, ndv, ndn), -1); continue; }
            }
            if (lev > KT[t]) {                              /* outgrew its tier: re-file */
                if (t == T_MID) {
                    if (nmidout == midoutcap) { midoutcap = midoutcap ? 2 * midoutcap : 1024; midout = xrealloc(midout, (size_t)midoutcap * sizeof(MidOut)); }
                    midout[nmidout++] = (MidOut){l, lev, mid_exit[k], mid_exp[k]};
                } else ppush(l, lev);
                continue;
            }
            if (t == T_TOP) top_exp[w] = top_exp[k];         /* keep the side arrays in step with the lines */
            if (t == T_UP) { up_exit[w] = up_exit[k]; up_exp[w] = up_exp[k]; }
            if (t == T_MID) { mid_exit[w] = mid_exit[k]; mid_exp[w] = mid_exp[k]; }
            a->v[w++] = l;
        }
        a->n = w;
    }
    /* 4. Re-file.  A pivoted line passes through (n, h), so its height at n + 1 is h + dv/dn.  The other
     *    lines are rising, so their level at n + 1 is at least the level at n, which is enough to choose
     *    a tier that is not too high. */
    for (i64 k = 0; k < nmidout; k++) mid_leave(midout[k].l, midout[k].lev, midout[k].te, midout[k].tp, n + 1);
    nmidout = 0;
    for (i64 k = 0; k < pendn; k++) {
        Line l = pend[k].l; i64 lev = pend[k].lev;
        if (lev < 0) { lev = h + ceildiv(l.dv, l.dn); if (lev < 0) lev = 0; }
        place(l, lev, n + 1);
    }
    return h;
}

/* Compute a(n).  bound: 0 in the main run; B2 inside simulate2(), where -1 means "a(n) > B2".
 * Leaves every line filed for step n + 1. */
static i64 step(i64 n, i64 bound) {
    /* 1. Levels of the T0 lines at step n, their histogram, and the advance of every T0 line to n + 1. */
    uint32_t hist[K0 + 2] = {0};
    for (i64 k = 0; k < t0n; k++) {
        L0 *l = &T0[k];
        i64 lev = l->Q + (l->R != 0); lev = lev < 0 ? 0 : lev;            /* ceil(Q + R/dn), at least 0 */
        levs[k] = lev;
        hist[lev <= K0 ? lev : K0 + 1]++;
        i64 R = l->R + l->rd, o = R >= l->dn;                             /* add the slope qd + rd/dn */
        l->R = o ? R - l->dn : R; l->Q += l->qd + o;
    }
    /* 2. Bit j of mask is set when v_n(j) <= j.  Every line with level <= K0 is in T0, so for j <= K0
     *    this count is complete, and the lowest set bit is a(n): the fast path. */
    uint32_t c = 0, mask = 0;
    for (int j = 0; j <= K0; j++) { c += hist[j]; mask |= (uint32_t)(c <= (uint32_t)j) << j; }
    i64 h;
    if (mask) {
        h = lowest_bit(mask);
        /* Pivot the visible T0 lines that pass below (n, h), in place.  The new slope (h - a)/(n - i) is
         * split into qd + rd/dn without a division in the common cases.  T0 lines that rose above K0
         * move to their tier. */
        for (i64 k = 0; k < t0n;) {
            i64 lev = levs[k];
            if (lev <= h) {
                L0 *l = &T0[k];
                i64 ndv = h - l->a, ndn = n - l->i;
                if (steeper(ndv, ndn, l->dv, l->dn)) {
                    i64 qd, rd;
                    if (ndn == 1) { qd = ndv; rd = 0; }
                    else if (ndv >= 0 && ndv < ndn) { qd = 0; rd = ndv; }
                    else if (ndv < 0 && -ndv <= ndn) { qd = -1; rd = ndv + ndn; }
                    else { qd = floordiv(ndv, ndn); rd = ndv - qd * ndn; }
                    l->dv = (int32_t)ndv; l->dn = ndn; l->qd = qd; l->rd = rd;
                    l->Q = h + qd; l->R = rd;                               /* height at n + 1: h + ndv/ndn */
                }
                k++;
            } else if (lev > K0) {
                int t = tier_of(lev);
                if (t) tier_push(t, l0_line(&T0[k]));
                T0[k] = T0[--t0n]; levs[k] = levs[t0n];
            } else k++;
        }
    } else {
        h = slow_path(n, bound);
        if (h < 0) return -1;
    }
    /* 3. The new building: its sight line starts with slope -h, the ground next door (level 0 at n + 1). */
    if (t0n == t0cap) t0_grow();
    T0[t0n++] = (L0){0, 0, -h, 0, 1, n, (int32_t)h, (int32_t)-h};
    /* 4. Falling lines that come down to K0 at step n + 1 join T0. */
    while (fn > 0 && F[0].D <= n + 1) {
        Line l = F[0].l;
        memmove(F, F + 1, (size_t)(fn - 1) * sizeof(FL)); fn--;
        t0_add(l, n + 1);
    }
    /* 5. Every 256 steps, maintain the tiers that have grown past their thresholds. */
    if (n >= nextmaint) {
        nextmaint = n + 256;
        for (int t = 1; t <= NT; t++) if (tier[t].n > maint[t]) maintain(t, n + 1);
    }
    return h;
}

/* =====================================================================================================
 *  MEMO: STORED RUNS
 *
 *  After a step m with a(m) > B (B = B1 or B2), consider the run of terms <= B that starts at s = m + 1
 *  and ends before e, the first later step with a term > B.  Its terms depend only on the lines that can
 *  have level <= B during it:
 *    - the T0 lines.  Every line with level <= B at step m was visible from (m, a(m)), passed below it,
 *      and pivoted through it; at s such a line is either rising and above a(m) > B, or falling and in T0
 *      or F.
 *    - the falling lines in F that come down to <= B during the run.
 *  Rising lines above B cannot come down, and buildings of height <= B cannot pivot them.  So the key of
 *  the run is the T0 lines plus the F lines that reach <= B within W steps, each written as
 *  (u = s - i, a, dv, dn), relative to the start, so that the same key recurs at different positions.
 *  The run is reused only if it is "pure": no F line outside the key reaches <= B before e.
 *
 *  An Entry stores the run: its terms, its statistics, and the lines it leaves behind at e (the key lines
 *  as they end up, plus the new buildings' lines), already split into T0, F and the tiers, with every
 *  precomputed number relative to e.  Replaying it means: remove the key lines (all of T0, and the key's F
 *  lines), insert the stored lines, and add the stored statistics.  No other line is touched.
 * ===================================================================================================== */
typedef struct { i64 u, a, dv, dn; } KeyLine;          /* a line relative to a time t: building i = t - u */
typedef struct { KeyLine *k; i64 n, cap; char *fk; i64 fkcap; } KeyBuf;   /* fk[j]: F line j is in the key */
typedef struct Entry {
    u64 h; i64 nk; KeyLine *key;                       /* the key (sorted by u) and its hash */
    i64 L, sum, maxv, B; unsigned char *terms;         /* the run: L terms <= B, their sum and maximum */
    i64 *cnt, *foff;                                   /* per height 0..B: count in the run, first offset (-1: none) */
    u64 pL, C[256], Cdone[4];                          /* hash over the run: h -> h*pL + C[h & 255]; C[r] valid if bit r of Cdone */
    i64 n0, nf, nt[NT + 1];                            /* how many lines it leaves in T0, F and each tier */
    L0 *t0;                                            /* T0 lines ready for step e (.i holds u = e - i) */
    Line *fl; i64 *fD;                                 /* F lines (.i holds u), and D - e */
    Line *tl[NT + 1];                                  /* tier lines (.i holds u) */
    i64 *top_dt;                                       /* top tier: expiry - e */
    i64 nshort, max_short_dt;                          /* tl[T_TOP][0..nshort) expire within BLK_HORIZON: the lazy block */
    i64 *up_exit_dt, *up_exp_dt;                       /* T_UP: exit - e, expiry - e */
    i64 *mid_exit_dt, *mid_exp_dt;                     /* T_MID: exit from T_UP - e, expiry - e */
    i64 bytes, uses;                                   /* memory charged to it; replays (halved at each eviction) */
} Entry;
static KeyBuf KB[3];                                   /* the key being looked up, per level */
static Entry **mtab[3]; static i64 mcap[3], mcount[3], mbytes[3], memcap[3];   /* open-addressing tables */
static i64 m_hit[3], m_miss[3], m_impure[3], m_bound[3], m_long[3], m_steps[3], m_clears[3];   /* statistics */

static int cmp_key(const void *x, const void *y) { const KeyLine *p = x, *q = y; return p->u < q->u ? -1 : p->u > q->u; }
/* FNV-style hash of a key. */
static u64 key_hash(const KeyLine *k, i64 nk) {
    u64 h = FNV_OFFSET ^ (u64)nk;
    for (i64 j = 0; j < nk; j++) {
        h = (h ^ (u64)k[j].u) * FNV_PRIME; h = (h ^ (u64)k[j].a) * FNV_PRIME;
        h = (h ^ (u64)(k[j].dv + (1 << 20))) * FNV_PRIME; h = (h ^ (u64)k[j].dn) * FNV_PRIME;
    }
    return h ^ (h >> 29);
}
static void kb_push(KeyBuf *kb, KeyLine r) {
    if (kb->n == kb->cap) { kb->cap = kb->cap ? 2 * kb->cap : 256; kb->k = xrealloc(kb->k, (size_t)kb->cap * sizeof(KeyLine)); }
    kb->k[kb->n++] = r;
}
/* The key of the run that starts at step s (right after a step taller than B): all T0 lines, and the F
 * lines that reach level <= B by step s + W.  *minD = the first step at which an F line outside the key
 * reaches <= B (the run is pure if it ends before then).  Each line has exactly one building, so sorting
 * by u gives a canonical order. */
static void extract_key(KeyBuf *kb, i64 s, i64 B, i64 W, i64 *minD) {
    kb->n = 0; *minD = INT64_MAX;
    for (i64 k = 0; k < t0n; k++) kb_push(kb, (KeyLine){s - T0[k].i, T0[k].a, T0[k].dv, T0[k].dn});
    if (kb->fkcap < fn) { kb->fkcap = 2 * fn + 64; kb->fk = xrealloc(kb->fk, (size_t)kb->fkcap); }
    for (i64 k = 0; k < fn; k++) {
        Line *l = &F[k].l;
        i64 D = l->i + ceildiv((i64)(l->a - B) * l->dn, -(i64)l->dv);    /* first step with level <= B */
        if (D <= s + W) { kb->fk[k] = 1; kb_push(kb, (KeyLine){s - l->i, l->a, l->dv, l->dn}); }
        else { kb->fk[k] = 0; if (D < *minD) *minD = D; }
    }
    qsort(kb->k, (size_t)kb->n, sizeof(KeyLine), cmp_key);
}

/* Build the entry for the run s..e-1 with the given terms, which leaves the given lines behind at e.
 * The lines are sorted into T0 / F / tiers for step e, with every step number stored relative to e. */
static Entry *entry_build(const KeyBuf *kb, i64 B, i64 s, i64 e, const unsigned char *terms, const PL *lines, i64 nl) {
    i64 L = e - s;
    Entry *E = xcalloc(1, sizeof(Entry));
    E->nk = kb->n; E->key = xrealloc(NULL, (size_t)(kb->n + 1) * sizeof(KeyLine)); memcpy(E->key, kb->k, (size_t)kb->n * sizeof(KeyLine));
    E->h = key_hash(kb->k, kb->n); E->L = L; E->B = B;
    E->terms = xrealloc(NULL, (size_t)L + 1); memcpy(E->terms, terms, (size_t)L);
    /* statistics of the run */
    E->cnt = xcalloc((size_t)B + 1, sizeof(i64)); E->foff = xrealloc(NULL, (size_t)(B + 1) * sizeof(i64));
    for (i64 v = 0; v <= B; v++) E->foff[v] = -1;
    E->maxv = -1;
    for (i64 j = 0; j < L; j++) {
        i64 v = terms[j]; E->sum += v; E->cnt[v]++;
        if (E->foff[v] < 0) E->foff[v] = j;
        if (v > E->maxv) E->maxv = v;
    }
    u64 pL = 1, b = FNV_PRIME; for (i64 e2 = L; e2; e2 >>= 1, b *= b) if (e2 & 1) pL *= b;   /* P^L by squaring */
    E->pL = pL;
    /* where each line goes at step e: -1 T0, -2 F, q > 0 tier q, 0 dropped (rising above HMAX) */
    static signed char *edst; static i64 edcap;
    if (edcap < nl + 1) { edcap = 2 * nl + 64; edst = xrealloc(edst, (size_t)edcap); }
    i64 c0 = 0, cf = 0, cq[NT + 1] = {0};
    for (i64 k = 0; k < nl; k++) {
        i64 lev = level_plain(lines[k].i, lines[k].a, lines[k].dv, lines[k].dn, e);
        int d = lev <= K0 ? -1 : lines[k].dv < 0 ? -2 : tier_of(lev);
        edst[k] = (signed char)d;
        if (d == -1) c0++; else if (d == -2) cf++; else if (d > 0) cq[d]++;
    }
    E->t0 = xrealloc(NULL, (size_t)(c0 + 1) * sizeof(L0));
    E->fl = xrealloc(NULL, (size_t)(cf + 1) * sizeof(Line)); E->fD = xrealloc(NULL, (size_t)(cf + 1) * sizeof(i64));
    for (int q = 1; q <= NT; q++) { E->tl[q] = xrealloc(NULL, (size_t)(cq[q] + 1) * sizeof(Line)); E->nt[q] = 0; }
    for (i64 k = 0; k < nl; k++) {
        i64 i = lines[k].i, a = lines[k].a, dv = lines[k].dv, dn = lines[k].dn;
        int d = edst[k];
        Line g = mkline(e - i, a, dv, dn);                        /* .i = u */
        if (d == -1) {                                           /* T0 form at e: Q + R/dn */
            i64 x = dv * (e - i), q = floordiv(x, dn), qd = floordiv(dv, dn);
            E->t0[E->n0++] = (L0){a + q, x - q * dn, qd, dv - qd * dn, dn, e - i, (int32_t)a, (int32_t)dv};
        } else if (d == -2) {                                    /* F: D relative to e */
            E->fD[E->nf] = i + ceildiv((a - K0) * dn, -dv) - e; E->fl[E->nf++] = g;
        } else if (d > 0) E->tl[d][E->nt[d]++] = g;
    }
    /* memory accounting: every array, plus allocator overhead for the ~24 blocks of an entry */
    E->bytes = (i64)sizeof(Entry) + kb->n * (i64)sizeof(KeyLine) + L + 16 * (B + 1) + E->n0 * (i64)sizeof(L0) + E->nf * ((i64)sizeof(Line) + 8);
    for (int q = 1; q <= NT; q++) E->bytes += (E->nt[q] + 1) * (i64)sizeof(Line);
    E->bytes += 24 * 32;
    /* the precomputed steps of the upper tiers, relative to e */
    E->top_dt = xrealloc(NULL, (size_t)(E->nt[T_TOP] + 1) * sizeof(i64));
    for (i64 k = 0; k < E->nt[T_TOP]; k++) { Line l = E->tl[T_TOP][k]; l.i = e - l.i; E->top_dt[k] = top_expiry(&l) - e; }
    E->bytes += E->nt[T_TOP] * 8;
    E->up_exit_dt = xrealloc(NULL, (size_t)(E->nt[T_UP] + 1) * sizeof(i64)); E->up_exp_dt = xrealloc(NULL, (size_t)(E->nt[T_UP] + 1) * sizeof(i64));
    for (i64 k = 0; k < E->nt[T_UP]; k++) { Line l = E->tl[T_UP][k]; l.i = e - l.i; E->up_exit_dt[k] = up_exit_step(&l) - e; E->up_exp_dt[k] = top_expiry(&l) - e; }
    E->bytes += 2 * E->nt[T_UP] * 8;
    E->mid_exit_dt = xrealloc(NULL, (size_t)(E->nt[T_MID] + 1) * sizeof(i64)); E->mid_exp_dt = xrealloc(NULL, (size_t)(E->nt[T_MID] + 1) * sizeof(i64));
    for (i64 k = 0; k < E->nt[T_MID]; k++) { Line l = E->tl[T_MID][k]; l.i = e - l.i; E->mid_exit_dt[k] = up_exit_step(&l) - e; E->mid_exp_dt[k] = top_expiry(&l) - e; }
    E->bytes += 2 * E->nt[T_MID] * 8;
    /* Put the short-lived top-tier lines first: tl[T_TOP][0..nshort) can be replayed as a lazy block. */
    {   i64 w = 0; E->max_short_dt = 0;
        for (i64 k = 0; k < E->nt[T_TOP]; k++) if (E->top_dt[k] <= BLK_HORIZON) {
            Line tl = E->tl[T_TOP][w]; i64 td = E->top_dt[w];
            E->tl[T_TOP][w] = E->tl[T_TOP][k]; E->top_dt[w] = E->top_dt[k]; E->tl[T_TOP][k] = tl; E->top_dt[k] = td;
            if (E->top_dt[w] > E->max_short_dt) E->max_short_dt = E->top_dt[w];
            w++;
        }
        E->nshort = w; }
    return E;
}
/* Copy every pending lazy block into the top tier (a slow step is about to count the top tier, or an
 * eviction is about to free the entries the blocks point into). */
static void blocks_materialize(void) {
    for (i64 b = 0; b < nblk; b++) {
        Entry *E = blk[b].E; i64 e = blk[b].e;
        for (i64 k = 0; k < E->nshort; k++) { Line l = E->tl[T_TOP][k]; l.i = e - l.i; top_push(l, e + E->top_dt[k]); }
    }
    nblk = 0;
}
/* Forget the blocks all of whose lines have expired by step m. */
static void blocks_expire(i64 m) {
    i64 w = 0;
    for (i64 b = 0; b < nblk; b++) if (blk[b].exp >= m) blk[w++] = blk[b];
    nblk = w;
}
static void entry_free(Entry *E) {
    free(E->key); free(E->terms); free(E->cnt); free(E->foff); free(E->t0); free(E->fl); free(E->fD);
    for (int q = 1; q <= NT; q++) free(E->tl[q]);
    free(E->top_dt); free(E->up_exit_dt); free(E->up_exp_dt); free(E->mid_exit_dt); free(E->mid_exp_dt);
    free(E);
}

/* ---- level 1: a new run is simulated with a plain list of its key lines -------------------------------- */
typedef struct { i64 i, a, dv, dn, Q, R, qd, rd; } SL;   /* a simulated line; height = Q + R/dn as in T0 */
static SL *sim; static i64 simn, simcap; static i64 *slev;
static PL *fin; static i64 finn, fincap;                 /* the lines a simulated run leaves behind */
static unsigned char *tb1; static i64 tb1cap;           /* the terms of the level-1 run being simulated */
static void sl_set(SL *x, i64 i, i64 a, i64 dv, i64 dn, i64 m) {      /* set up line (i, a, dv, dn) for step m */
    i64 xx = dv * (m - i), q = floordiv(xx, dn), qd = floordiv(dv, dn);
    *x = (SL){i, a, dv, dn, a + q, xx - q * dn, qd, dv - qd * dn};
}
static void fin_push(PL c) {
    if (finn == fincap) { fincap = fincap ? 2 * fincap : 4096; fin = xrealloc(fin, (size_t)fincap * sizeof(PL)); }
    fin[finn++] = c;
}
/* Simulate the level-1 run starting at s from its key alone, the same way step() works: levels, the least
 * h with v(h) <= h, pivots, a new line per building.  The run ends at the first step where no h <= B1
 * works.  Lines that rise above B1 can play no further part and are set aside.  Returns NULL if the run
 * is longer than LMAX1. */
static Entry *simulate1(const KeyBuf *kb, i64 s) {
    const i64 B = LB[1];
    simn = 0; finn = 0;
    for (i64 j = 0; j < kb->n; j++) {
        if (simn == simcap) { simcap = simcap ? 2 * simcap : 1024; sim = xrealloc(sim, (size_t)simcap * sizeof(SL)); slev = xrealloc(slev, (size_t)simcap * sizeof(i64)); }
        sl_set(&sim[simn++], s - kb->k[j].u, kb->k[j].a, kb->k[j].dv, kb->k[j].dn, s);
    }
    i64 t;
    for (t = s;; t++) {
        if (t - s >= LMAX[1]) return NULL;
        i64 hist[B1 + 2]; memset(hist, 0, sizeof hist);
        for (i64 k = 0; k < simn; k++) {
            i64 lev = sim[k].Q + (sim[k].R != 0); lev = lev < 0 ? 0 : lev;
            slev[k] = lev; if (lev <= B) hist[lev]++;
        }
        i64 c = 0, h = -1;
        for (i64 j = 0; j <= B; j++) { c += hist[j]; if (c <= j) { h = j; break; } }
        if (h < 0) break;                                    /* step t is taller than B: the run ends */
        if (c != h) die("internal error: simulated v(h) != h", t);
        if (t - s >= tb1cap) { tb1cap = tb1cap ? 2 * tb1cap : 1 << 16; tb1 = xrealloc(tb1, (size_t)tb1cap); }
        tb1[t - s] = (unsigned char)h;
        for (i64 k = 0; k < simn;) {
            SL *x = &sim[k]; i64 lev = slev[k];
            if (lev <= h) {
                i64 ndv = h - x->a, ndn = t - x->i;
                if (steeper(ndv, ndn, x->dv, x->dn)) { sl_set(x, x->i, x->a, ndv, ndn, t + 1); k++; continue; }
            } else if (lev > B && x->dv >= 0) {              /* rose above B: frozen for the rest of the run */
                fin_push((PL){x->i, x->a, x->dv, x->dn});
                sim[k] = sim[--simn]; slev[k] = slev[simn];
                continue;
            }
            i64 R = x->R + x->rd, o = R >= x->dn; x->R = o ? R - x->dn : R; x->Q += x->qd + o;   /* advance */
            k++;
        }
        if (simn == simcap) { simcap = 2 * simcap; sim = xrealloc(sim, (size_t)simcap * sizeof(SL)); slev = xrealloc(slev, (size_t)simcap * sizeof(i64)); }
        sim[simn++] = (SL){t, h, -h, 1, 0, 0, -h, 0};          /* the new building */
    }
    for (i64 k = 0; k < simn; k++) fin_push((PL){sim[k].i, sim[k].a, sim[k].dv, sim[k].dn});
    return entry_build(kb, B, s, t, tb1, fin, finn);
}

/* ---- the hash tables --------------------------------------------------------------------------------- */
/* Look up a key (linear probing). */
static Entry *memo_find(int lv, const KeyBuf *kb, u64 h) {
    for (i64 p = (i64)(h & (u64)(mcap[lv] - 1));; p = (p + 1) & (mcap[lv] - 1)) {
        Entry *E = mtab[lv][p];
        if (!E) return NULL;
        if (E->h == h && E->nk == kb->n && memcmp(E->key, kb->k, (size_t)kb->n * sizeof(KeyLine)) == 0) return E;
    }
}
/* Insert a new entry.  If the level's memory budget would be exceeded, first evict the least-used
 * entries: raise the bar on the use count until at most 60% of the budget remains, then rehash the
 * survivors and halve their counts.  The table doubles whenever it becomes half full. */
static void memo_insert(int lv, Entry *E) {
    if (mbytes[lv] + E->bytes > memcap[lv]) {
        if (lv == 2 && nblk) blocks_materialize();          /* blocks point into level-2 entries */
        for (int round = 0; round < 40; round++) {
            u64 thr = round < 30 ? (2ULL << (2 * round)) : UINT64_MAX;
            i64 keep = 0;
            for (i64 p = 0; p < mcap[lv]; p++) {
                Entry *X = mtab[lv][p];
                if (!X) continue;
                if ((u64)X->uses < thr) { i64 b = X->bytes; entry_free(X); mtab[lv][p] = NULL; mcount[lv]--; mbytes[lv] -= b; }
                else keep++;
            }
            if (mbytes[lv] <= memcap[lv] / 10 * 6 || keep == 0) break;
        }
        Entry **ot = mtab[lv];
        mtab[lv] = xcalloc((size_t)mcap[lv], sizeof(Entry *));
        for (i64 p = 0; p < mcap[lv]; p++) if (ot[p]) {
            Entry *X = ot[p]; X->uses /= 2;
            i64 q = (i64)(X->h & (u64)(mcap[lv] - 1)); while (mtab[lv][q]) q = (q + 1) & (mcap[lv] - 1);
            mtab[lv][q] = X;
        }
        free(ot);
        m_clears[lv]++;
    }
    if (2 * (mcount[lv] + 1) > mcap[lv]) {
        i64 oc = mcap[lv]; Entry **ot = mtab[lv];
        mcap[lv] = oc ? 2 * oc : 1 << 14; mtab[lv] = xcalloc((size_t)mcap[lv], sizeof(Entry *));
        for (i64 p = 0; p < oc; p++) if (ot[p]) {
            i64 q = (i64)(ot[p]->h & (u64)(mcap[lv] - 1)); while (mtab[lv][q]) q = (q + 1) & (mcap[lv] - 1);
            mtab[lv][q] = ot[p];
        }
        free(ot);
    }
    i64 q = (i64)(E->h & (u64)(mcap[lv] - 1)); while (mtab[lv][q]) q = (q + 1) & (mcap[lv] - 1);
    mtab[lv][q] = E; mcount[lv]++; mbytes[lv] += E->bytes;
}

/* ---- replay ------------------------------------------------------------------------------------------ */
/* Replace the key lines by the lines the stored run leaves behind (the engine state after the run).
 * T0 consisted of key lines only, so it is replaced as a whole.  At level 2 in the main engine, the
 * short-lived top-tier lines are not copied: a block pointing at them is recorded instead. */
static void memo_apply_state(const KeyBuf *kb, Entry *E, i64 s, int lv) {
    i64 e = s + E->L;
    t0n = 0;
    {   i64 w = 0; for (i64 k = 0; k < fn; k++) if (!kb->fk[k]) F[w++] = F[k]; fn = w; }
    while (t0cap < E->n0 + 1) t0_grow();
    for (i64 k = 0; k < E->n0; k++) { T0[k] = E->t0[k]; T0[k].i = e - E->t0[k].i; }
    t0n = E->n0;
    for (i64 k = 0; k < E->nf; k++) { Line l = E->fl[k]; l.i = e - l.i; f_insert(l, e + E->fD[k]); }
    for (int q = 1; q <= NT; q++) {
        Vec *a = &tier[q]; i64 m = E->nt[q];
        if (!m) continue;
        while (a->n + m > a->cap) { a->cap = a->cap ? 2 * a->cap : 1024; a->v = xrealloc(a->v, (size_t)a->cap * sizeof(Line)); }
        i64 k0 = 0;
        if (q == T_TOP && use_blocks && lv == 2 && E->nshort > 0) {
            if (nblk == blkcap) { blkcap = blkcap ? 2 * blkcap : 1024; blk = xrealloc(blk, (size_t)blkcap * sizeof(Block)); }
            blk[nblk++] = (Block){E, e, e + E->max_short_dt};
            k0 = E->nshort;
        }
        Line *dst = a->v + a->n, *src = E->tl[q];
        for (i64 k = k0; k < m; k++) { dst[k - k0] = src[k]; dst[k - k0].i = e - src[k].i; }
        if (q == T_TOP) {
            if (top_expcap < a->cap) { top_expcap = a->cap; top_exp = xrealloc(top_exp, (size_t)top_expcap * sizeof(i64)); }
            for (i64 k = k0; k < m; k++) top_exp[a->n + k - k0] = e + E->top_dt[k];
        }
        if (q == T_UP) {
            if (up_cap < a->cap) { up_cap = a->cap; up_exit = xrealloc(up_exit, (size_t)up_cap * sizeof(i64)); up_exp = xrealloc(up_exp, (size_t)up_cap * sizeof(i64)); }
            for (i64 k = 0; k < m; k++) { up_exit[a->n + k] = e + E->up_exit_dt[k]; up_exp[a->n + k] = e + E->up_exp_dt[k]; }
        }
        if (q == T_MID) {
            if (mid_cap < a->cap) { mid_cap = a->cap; mid_exit = xrealloc(mid_exit, (size_t)mid_cap * sizeof(i64)); mid_exp = xrealloc(mid_exp, (size_t)mid_cap * sizeof(i64)); }
            for (i64 k = 0; k < m; k++) { mid_exit[a->n + k] = e + E->mid_exit_dt[k]; mid_exp[a->n + k] = e + E->mid_exp_dt[k]; }
        }
        a->n += m - k0;
    }
}
static Entry *simulate2(const KeyBuf *kb, i64 s);
/* The entry for the level-lv run that starts at s, if it may be replayed: it must be pure, and the run
 * must end by step 'limit' (so that a replay never jumps over a reporting point).  New runs are simulated
 * and stored. */
static Entry *memo_try(int lv, i64 s, i64 limit) {
    KeyBuf *kb = &KB[lv];
    i64 minD; extract_key(kb, s, LB[lv], LW[lv], &minD);
    u64 h = key_hash(kb->k, kb->n);
    Entry *E = mcap[lv] ? memo_find(lv, kb, h) : NULL;
    if (E) { m_hit[lv]++; E->uses++; }
    else {
        E = lv == 1 ? simulate1(kb, s) : simulate2(kb, s);
        if (!E) { m_long[lv]++; return NULL; }
        memo_insert(lv, E); m_miss[lv]++;
    }
    i64 e = s + E->L;
    if (minD < e) { m_impure[lv]++; return NULL; }      /* a falling line outside the key would interfere */
    if (e > limit) { m_bound[lv]++; return NULL; }      /* the run would cross a reporting point */
    return E;
}

/* ---- level 2: a new run is computed by a private engine on just its key lines ---------------------------- */
static unsigned char *tb2; static i64 tb2cap;            /* the terms of the level-2 run being simulated */
static void tb2_put(i64 off, const unsigned char *b, i64 L) {
    while (off + L > tb2cap) { tb2cap = tb2cap ? 2 * tb2cap : 1 << 20; tb2 = xrealloc(tb2, (size_t)tb2cap); }
    memcpy(tb2 + off, b, (size_t)L);
}
/* Save the main engine, start an empty one, file the key lines in it, and run it -- with level-1 replays
 * after every term > B1 -- until the first step taller than B2, which step(n, B2) reports as -1.  Then
 * collect every line left (they become the entry's lines), and restore the main engine.  Returns NULL if
 * the run is longer than LMAX2. */
static Entry *simulate2(const KeyBuf *kb, i64 s) {
    Eng saved; eng_save(&saved); eng_clear(s);
    for (i64 j = 0; j < kb->n; j++) {
        Line l = mkline(s - kb->k[j].u, kb->k[j].a, kb->k[j].dv, kb->k[j].dn);
        place(l, level_plain(l.i, l.a, l.dv, l.dn, s), s);
    }
    i64 n = s, lim = s + LMAX[2]; int at1 = 0, ok = 1;
    for (;;) {
        if (n >= lim) { ok = 0; break; }
        if (at1) {
            at1 = 0;
            Entry *E1 = memo_try(1, n, lim);
            if (E1) {
                memo_apply_state(&KB[1], E1, n, 1); tb2_put(n - s, E1->terms, E1->L); n += E1->L;
                if (n >= lim) { ok = 0; break; }
            }
        }
        i64 h = step(n, LB[2]);
        if (h < 0) break;                                    /* step n is taller than B2: the run ends */
        unsigned char b = (unsigned char)h; tb2_put(n - s, &b, 1);
        at1 = h > LB[1];
        n++;
    }
    Entry *E = NULL;
    if (ok) {
        finn = 0;
        for (i64 k = 0; k < t0n; k++) fin_push((PL){T0[k].i, T0[k].a, T0[k].dv, T0[k].dn});
        for (i64 k = 0; k < fn; k++) fin_push((PL){F[k].l.i, F[k].l.a, F[k].l.dv, F[k].l.dn});
        for (int t = 1; t <= NT; t++) for (i64 k = 0; k < tier[t].n; k++) { Line *l = &tier[t].v[k]; fin_push((PL){l->i, l->a, l->dv, l->dn}); }
        E = entry_build(kb, LB[2], s, n, tb2, fin, finn);
    }
    eng_free(); eng_load(&saved);
    return E;
}

/* =====================================================================================================
 *  STATISTICS AND OUTPUT
 * ===================================================================================================== */
static i64 cnt[HMAX + 1], first[HMAX + 1];   /* occurrences of each height so far; index of its first occurrence (0: none) */
static i64 maxa = -1, sum = 0;               /* largest term so far; sum of the terms so far */
static u64 hash = FNV_OFFSET;                /* FNV-1a over the terms: hash = (hash ^ a(n)) * FNV_PRIME for n = 1, 2, ... */
#define MAXREC 256
static i64 rec_h[MAXREC], rec_n[MAXREC]; static int nrec;   /* the records: rec_h[k] = a(rec_n[k]) */
static int quiet;

/* Output.  The terms are formatted into a 16 MB buffer.  For b-files the index is kept as a decimal string
 * and incremented in place, and the terms below 256 (including every term of a replayed run) come from a
 * table, so formatting takes a few nanoseconds per term. */
enum { FMT_BFILE, FMT_COMMA, FMT_NONE };
static int fmt = FMT_BFILE;
static FILE *outf;
static i64 out_start = 1;                    /* first index to write */
#define OBUF (1 << 24)
static char *obuf; static size_t obn;
static char idxs[32]; static int idxlen;     /* decimal digits of the index of the next term to be written */
static char tstr[256][4]; static unsigned char tlen[256];   /* decimal strings of 0..255 */
static i64 out_count;                        /* terms written so far */

static void out_flush(void) {
    if (obn && fwrite(obuf, 1, obn, outf) != obn) die("cannot write the output (disk full?)", 0);
    obn = 0;
}
static void out_init(void) {
    obuf = xrealloc(NULL, OBUF);
    for (int v = 0; v < 256; v++) tlen[v] = (unsigned char)snprintf(tstr[v], 4, "%d", v);
    idxlen = snprintf(idxs, sizeof idxs, "%lld", (long long)out_start);
}
/* Add 1 to the decimal index string. */
static inline void idx_inc(void) {
    int k = idxlen - 1;
    while (k >= 0 && idxs[k] == '9') idxs[k--] = '0';
    if (k >= 0) idxs[k]++;
    else { memmove(idxs + 1, idxs, (size_t)idxlen); idxs[0] = '1'; idxlen++; }
}
/* Write the next term (its index is the decimal string idxs). */
static inline void out_term(i64 v) {
    if (obn + 64 > OBUF) out_flush();
    char *p = obuf + obn;
    if (fmt == FMT_BFILE) { memcpy(p, idxs, 16); p += idxlen; *p++ = ' '; }   /* indices have at most 13 digits */
    else if (out_count) { *p++ = ','; *p++ = ' '; }
    if (v < 256) { memcpy(p, tstr[v], 4); p += tlen[v]; }
    else p += snprintf(p, 24, "%lld", (long long)v);                         /* rare: terms >= 256 */
    if (fmt == FMT_BFILE) { *p++ = '\n'; idx_inc(); }
    obn = (size_t)(p - obuf); out_count++;
}
/* Write the terms s..s+L-1 of a replayed run (those with index >= out_start). */
static void out_run(i64 s, const unsigned char *t, i64 L) {
    for (i64 j = out_start > s ? out_start - s : 0; j < L; j++) out_term(t[j]);
}
static void out_close(void) {
    if (fmt == FMT_COMMA && out_count) obuf[obn++] = '\n';
    out_flush();
    if (outf == stdout ? fflush(stdout) != 0 : fclose(outf) != 0) die("cannot write the output (disk full?)", 0);
}

/* ---- the direct computation (self-test) -------------------------------------------------------------- */
/* a(1..T) straight from the definition: no sight lines, no tiers, no memo.  For each candidate height h at
 * position n, walk back from n - 1 and count the rooftops visible from (n, h).  Seen from the viewer,
 * rooftop k is at relative height a(k) - h and distance n - k, and it is visible iff its slope
 * (a(k) - h)/(n - k) is at least the steepest slope of the rooftops between it and the viewer (equal
 * slopes are collinear, which counts as visible).  The first h with at most h visible rooftops is a(n).
 * O(T^2) in all; well under a second for T = 10^4. */
static int32_t *direct; static i64 directT;
static void direct_compute(i64 T) {
    direct = xrealloc(NULL, (size_t)(T + 1) * sizeof(int32_t)); directT = T;
    int32_t *a = direct;
    for (i64 n = 1; n <= T; n++) {
        for (i64 h = 0;; h++) {
            i64 seen = 0, bn = 0, bd = 0;                    /* steepest slope so far: bn/bd; bd = 0: none yet */
            for (i64 k = n - 1; k >= 1 && seen <= h; k--) {
                i64 num = a[k] - h, den = n - k;
                if (bd == 0 || num * bd >= bn * den) seen++;
                if (bd == 0 || num * bd > bn * den) { bn = num; bd = den; }
            }
            if (seen <= h) { a[n] = (int32_t)h; break; }
        }
    }
}
NORETURN static void direct_mismatch(i64 n, i64 fast) {
    fprintf(stderr, "A400000_1T: SELF-TEST FAILED: a(%lld) = %d by the definition but %lld by the fast engine\n",
            (long long)n, direct[n], (long long)fast);
    exit(1);
}

/* ---- statistics -------------------------------------------------------------------------------------- */
static void new_record(i64 h, i64 n) {
    if (nrec < MAXREC) { rec_h[nrec] = h; rec_n[nrec] = n; nrec++; }
    if (!quiet) fprintf(stderr, "record: a(%lld) = %lld\n", (long long)n, (long long)h);
}
/* Statistics and output for a term computed by step(). */
static inline void term_done(i64 n, i64 h) {
    cnt[h]++; sum += h;
    hash = (hash ^ (u64)h) * FNV_PRIME;
    if (!first[h]) first[h] = n;
    if (h > maxa) { maxa = h; new_record(h, n); }
    if (fmt != FMT_NONE && n >= out_start) out_term(h);
    if (n <= directT && h != direct[n]) direct_mismatch(n, h);
}
/* Statistics and output for a replayed run of L terms starting at s, in O(B) time plus the output. */
static void run_done(Entry *E, i64 s) {
    u64 r0 = hash & 255;
    if (!(E->Cdone[r0 >> 6] >> (r0 & 63) & 1)) {    /* first replay with this low byte: one pass over the run */
        u64 acc = 0, r = r0;
        for (i64 j = 0; j < E->L; j++) {
            u64 x = E->terms[j];
            acc = (acc + ((r ^ x) - r)) * FNV_PRIME;     /* (h ^ x) * P = (h + (r ^ x) - r) * P, r = h mod 256 */
            r = ((r ^ x) * FNV_PRIME) & 255;
        }
        E->C[r0] = acc; E->Cdone[r0 >> 6] |= 1ULL << (r0 & 63);
    }
    hash = hash * E->pL + E->C[r0];
    sum += E->sum;
    for (i64 v = 0; v <= E->B; v++) {
        if (!E->cnt[v]) continue;
        cnt[v] += E->cnt[v];
        if (!first[v]) first[v] = s + E->foff[v];
    }
    /* A replayed run follows a term taller than all of its own terms, so it can never contain a record. */
    if (E->maxv > maxa) die("internal error: record inside a replayed run", s);
    if (fmt != FMT_NONE && s + E->L > out_start) out_run(s, E->terms, E->L);
    if (s <= directT) for (i64 j = 0; j < E->L && s + j <= directT; j++) if (E->terms[j] != direct[s + j]) direct_mismatch(s + j, E->terms[j]);
}

/* ---- reference values -------------------------------------------------------------------------------- */
/* Sum, maximum and FNV-1a hash of a(1..n), from the computation behind the published b-files (Mac Studio,
 * 2026; every term in this range was also recomputed without memo on other machines).  The sums at 10^k
 * are A397740(10^k).  The hashes at 10^k up to 10^6 were also checked with an independent script, and
 * those from 10^7 on were recomputed from the stored terms. */
typedef struct { i64 n, sum, max; u64 hash; } Ref;
static const Ref REF[] = {
    {10LL, 14LL, 3, 0x657761b6a2c099a9ULL},
    {100LL, 244LL, 11, 0xed8e6ff84e380bbfULL},
    {1000LL, 2678LL, 21, 0x39ea4d8a201c2017ULL},
    {10000LL, 29015LL, 165, 0x572f36381a4716acULL},
    {100000LL, 292524LL, 355, 0xf1d776dd3ff4cddbULL},
    {1000000LL, 2931483LL, 372, 0xbba0beb50c67c624ULL},
    {10000000LL, 29328290LL, 1148, 0x7989e09ab2ca7f7fULL},
    {100000000LL, 293501236LL, 1151, 0x6eb0cb0835b3e64dULL},
    {1000000000LL, 2935127340LL, 1910, 0xf23f1dfb446bf927ULL},
    {1073741824LL, 3151571412LL, 1910, 0x1c6361a2e1b8ea07ULL},             /* 2^30 */
    {2147483648LL, 6303103020LL, 1910, 0xaf3a740f4287df87ULL},             /* 2^31 */
    {4294967296LL, 12606342566LL, 1910, 0xf74f4aad91ce2439ULL},            /* 2^32 */
    {8589934592LL, 25212692192LL, 1968, 0xaa59d8c2b088d1e3ULL},            /* 2^33 */
    {10000000000LL, 29351433668LL, 1968, 0x014dd52e4d354cfbULL},
    {17179869184LL, 50425410340LL, 1968, 0xe033943b0cddadc9ULL},           /* 2^34 */
    {34359738368LL, 100850927198LL, 1968, 0x9a30c22520d39b69ULL},          /* 2^35 */
    {68719476736LL, 201701904814LL, 1998, 0xa88608c4ffccff9dULL},          /* 2^36 */
    {100000000000LL, 293514796838LL, 1998, 0x12afc1ac10f657ebULL},
    {137438953472LL, 403403644269LL, 1998, 0x7f1eba79ab61476aULL},         /* 2^37 */
    {274877906944LL, 806803932243LL, 296961, 0x2acc2a5e7abe3c0cULL},       /* 2^38 */
    {549755813888LL, 1613597082168LL, 296961, 0x5488ede1aa01c9c1ULL},      /* 2^39 */
    {999653638144LL, 2934092514062LL, 296961, 0xf0ca8a1c4cf43ed3ULL},      /* 931 * 2^30 */
    {1000000000000LL, 2935109083112LL, 296961, 0xe7afdb6afee71aa5ULL},
    {1099511627776LL, 3227184873472LL, 296961, 0x495f5d04e3709789ULL},     /* 2^40 */
    {2199023255552LL, 6454359498151LL, 296961, 0x1b4f0e53288558a2ULL},     /* 2^41 */
    {3298534883328LL, 9681531556213LL, 296961, 0x3a9905c1258732a0ULL},     /* 3 * 2^40 */
    {4396972769280LL, 12905553216530LL, 296961, 0xba63c7b5996d1dbfULL},    /* 4095 * 2^30, the last one below 2^42 */
};
#define NREF ((int)(sizeof REF / sizeof REF[0]))
static int nref_ok;
static void ref_check(const Ref *r) {
    if (sum != r->sum || maxa != r->max || hash != r->hash) {
        fprintf(stderr, "A400000_1T: REFERENCE CHECK FAILED at n = %lld: sum %lld, max %lld, hash %016llx;"
                " expected sum %lld, max %lld, hash %016llx\n", (long long)r->n, (long long)sum, (long long)maxa,
                (unsigned long long)hash, (long long)r->sum, (long long)r->max, (unsigned long long)r->hash);
        exit(1);
    }
    nref_ok++;
    if (!quiet) fprintf(stderr, "check: a(1..%lld) has sum %lld, max %lld, hash %016llx: matches the reference values\n", (long long)r->n,
                        (long long)sum, (long long)maxa, (unsigned long long)hash);
}

/* =====================================================================================================
 *  MAIN
 * ===================================================================================================== */
static void usage(FILE *f) {
    fprintf(f,
        "usage: A400000_1T [options]\n"
        "Computes a(1..N) of OEIS A400000, the city-building sequence.\n"
        "  -n N       number of terms (default 10000); e.g. 1000000, 1e12 or 2^40; N < 2^42\n"
        "  -o FILE    write the terms to FILE (default: standard output)\n"
        "  -f FORMAT  b = b-file, lines \"n a(n)\" (default); c = comma-separated list; none = no terms\n"
        "  -s START   write only a(START..N) (all terms are still computed)\n"
        "  -S FILE    write statistics to FILE at the end (records; first index and count of each height)\n"
        "  -p SEC     progress on stderr at most every SEC seconds (default 10; 0 = at every 2^30 terms)\n"
        "  -q         quiet: nothing on stderr except errors\n"
        "  -t T       check a(1..T) against a direct computation of the definition (default 10000; 0 = off)\n"
        "  -m L       memo levels: 2 (default), 1 or 0 (0 = no memo: much slower, an independent cross-check)\n"
        "  -M GB      memory budget for the memo tables in GiB (default 8)\n"
        "  -h         this help\n");
}
/* A count such as 1000000, 1e12, 2.5e9 or 2^40 (it must be a whole number). */
static i64 parse_count(const char *s, const char *opt) {
    char *end; double v;
    const char *caret = strchr(s, '^');
    int digits = *s != 0; for (const char *p = s; *p; p++) if (*p < '0' || *p > '9') digits = 0;
    if (digits && strlen(s) <= 18) return strtoll(s, NULL, 10);
    if (caret) {
        double b = strtod(s, &end); if (end != caret) goto bad;
        double x = strtod(caret + 1, &end); if (*end || end == caret + 1) goto bad;
        v = pow(b, x);
    } else { v = strtod(s, &end); if (*end || end == s) goto bad; }
    if (!(v >= 0) || v > 9e18 || v != floor(v)) goto bad;
    return (i64)v;
bad:
    fprintf(stderr, "A400000_1T: %s needs a whole number, not \"%s\"\n", opt, s);
    exit(1);
}
/* h:mm:ss */
static void hms(double t, char *buf, size_t z) {
    if (t < 0 || t > 1e9) t = 0;
    long s = (long)(t + 0.5);
    snprintf(buf, z, "%ld:%02ld:%02ld", s / 3600, s / 60 % 60, s % 60);
}
static double t_start, t_last, prog_every = 10; static i64 n_last;
/* Progress line at a multiple of 2^30 (at most every prog_every seconds). */
static void progress(i64 n, i64 N) {
    if (quiet || prog_every < 0) return;
    double t = now();
    if (prog_every > 0 && t - t_last < prog_every) return;
    char el[32], eta[32];
    hms(t - t_start, el, sizeof el); hms((t - t_start) * (double)(N - n) / (double)n, eta, sizeof eta);
    fprintf(stderr, "[%s] n = %lld (%.1f%%)  %.2f ns/term  max %lld  ETA %s  sum %lld  hash %016llx\n", el, (long long)n,
            100.0 * (double)n / (double)N, 1e9 * (t - t_last) / (double)(n - n_last), (long long)maxa, eta, (long long)sum,
            (unsigned long long)hash);
    t_last = t; n_last = n;
}
static i64 smallest_unseen(void) { i64 m = 0; while (m <= HMAX && first[m]) m++; return m; }
static i64 distinct_heights(void) { i64 d = 0; for (i64 v = 0; v <= HMAX; v++) d += cnt[v] > 0; return d; }
/* The statistics file (-S). */
static void write_stats(const char *path, i64 N) {
    FILE *f = fopen(path, "w");
    if (!f) die("cannot open the statistics file", 0);
    fprintf(f, "# Statistics of A400000(1..%lld), the city-building sequence, computed by A400000_1T.c\n", (long long)N);
    fprintf(f, "terms %lld\n", (long long)N);
    fprintf(f, "sum %lld\n", (long long)sum);
    fprintf(f, "hash %016llx\n", (unsigned long long)hash);
    fprintf(f, "max %lld at %lld\n", (long long)maxa, (long long)first[maxa]);
    fprintf(f, "distinct_heights %lld\n", (long long)distinct_heights());
    fprintf(f, "smallest_unseen_height %lld\n", (long long)smallest_unseen());
    fprintf(f, "#\n# record k height index        (A399949(k) = height, A399950(k) = index)\n");
    for (int k = 0; k < nrec; k++) fprintf(f, "record %d %lld %lld\n", k + 1, (long long)rec_h[k], (long long)rec_n[k]);
    fprintf(f, "#\n# height h first count         (first = A399763(h), the index of the first building of height h;\n"
               "#                              count = number of n <= %lld with a(n) = h.  Sorted by first, these\n"
               "#                              lines give A397493 (h) and A400121 (first).)\n", (long long)N);
    for (i64 v = 0; v <= HMAX; v++) if (cnt[v]) fprintf(f, "height %lld %lld %lld\n", (long long)v, (long long)first[v], (long long)cnt[v]);
    if (fclose(f) != 0) die("cannot write the statistics file", 0);
}

int main(int argc, char **argv) {
    i64 N = 10000, selftest = 10000; int memo_levels = 2; double memgb = 8;
    const char *outpath = NULL, *statspath = NULL;
    /* ---- options */
    for (int k = 1; k < argc; k++) {
        const char *o = argv[k];
        if (!strcmp(o, "-h") || !strcmp(o, "--help")) { usage(stdout); return 0; }
        if (!strcmp(o, "-q")) { quiet = 1; continue; }
        if (o[0] != '-' || !o[1] || o[2] || k + 1 >= argc) { usage(stderr); return 1; }
        const char *v = argv[++k];
        switch (o[1]) {
            case 'n': N = parse_count(v, "-n"); break;
            case 'o': outpath = v; break;
            case 'f': if (v[0] == 'b') fmt = FMT_BFILE; else if (v[0] == 'c') fmt = FMT_COMMA; else if (v[0] == 'n') fmt = FMT_NONE;
                      else { fprintf(stderr, "A400000_1T: -f takes b, c or none\n"); return 1; }
                      break;
            case 's': out_start = parse_count(v, "-s"); break;
            case 'S': statspath = v; break;
            case 'p': prog_every = atof(v); break;
            case 't': selftest = parse_count(v, "-t"); break;
            case 'm': memo_levels = atoi(v); if (memo_levels < 0 || memo_levels > 2) { fprintf(stderr, "A400000_1T: -m takes 0, 1 or 2\n"); return 1; } break;
            case 'M': memgb = atof(v); if (!(memgb > 0)) { fprintf(stderr, "A400000_1T: -M needs a positive size in GiB\n"); return 1; } break;
            default: usage(stderr); return 1;
        }
    }
    if (N < 1 || N >= NLIMIT) { fprintf(stderr, "A400000_1T: N must be between 1 and 2^42 - 1 = %lld\n", (long long)(NLIMIT - 1)); return 1; }
    if (out_start < 1) out_start = 1;
    memcap[1] = (i64)(memgb * 0.2 * 1073741824.0); memcap[2] = (i64)(memgb * 0.8 * 1073741824.0);

    /* ---- set up */
    build_ttab();
    levhist = xcalloc(HMAX + 2, sizeof(i64));
    for (int t = 1; t <= NT; t++) maint[t] = MAINT_ADD;
    nextmaint = 1; use_blocks = 1;
    if (fmt != FMT_NONE) {
        outf = outpath && strcmp(outpath, "-") ? fopen(outpath, "wb") : stdout;
        if (!outf) die("cannot open the output file", 0);
        out_init();
    }
    if (selftest > 0) direct_compute(selftest < N ? selftest : N);
    if (!quiet) {
        char from[64] = "";
        if (out_start > 1 && fmt != FMT_NONE) snprintf(from, sizeof from, " (terms from a(%lld) on)", (long long)out_start);
        fprintf(stderr, "A400000_1T: computing a(1..%lld); %s%s%s; memo levels %d, memo budget %.3g GiB; HMAX %d; %s division\n",
                (long long)N, fmt == FMT_NONE ? "no term output" : fmt == FMT_BFILE ? "b-file to " : "comma list to ",
                fmt == FMT_NONE ? "" : outpath && strcmp(outpath, "-") ? outpath : "stdout", from,
                memo_levels, memgb, HMAX, LEVEL_INT ? "integer" : "floating-point");
    }

    /* ---- the main loop.  'event' is the next n at which the statistics must be exact (a multiple of 2^30,
     *      a reference point, or N); a replay never jumps over it. */
    t_start = t_last = now(); n_last = 0;
    int ri = 0;
    i64 next_report = REPORT_EVERY;
    i64 event = N < next_report ? N : next_report;
    if (REF[0].n < event) event = REF[0].n;
    i64 prev = 0;                                     /* the previous term */
    for (i64 n = 1; n <= N; n++) {
        /* After a term > B1, the run that follows may be replayed: at level 2 if the term was > B2 (if that
         * fails, at level 1), at level 1 if it was > B1.  After the replay, n is the first step after the run,
         * whose term is taller than B and is computed by step() below. */
        if (memo_levels >= 1 && prev > B1) {
            Entry *E = NULL; int lv = 0;
            if (memo_levels >= 2 && prev > B2) { E = memo_try(2, n, event); lv = 2; }
            if (!E) { E = memo_try(1, n, event); lv = 1; }
            if (E) { memo_apply_state(&KB[lv], E, n, lv); run_done(E, n); m_steps[lv] += E->L; n += E->L; }
        }
        i64 h = step(n, 0);
        term_done(n, h);
        prev = h;
        if (n == event) {                             /* exact statistics: report and check */
            if (n == next_report) { progress(n, N); next_report += REPORT_EVERY; }
            while (ri < NREF && REF[ri].n <= n) { if (REF[ri].n == n) ref_check(&REF[ri]); ri++; }
            event = N < next_report ? N : next_report;
            if (ri < NREF && REF[ri].n < event) event = REF[ri].n;
        }
    }
    double secs = now() - t_start;
    if (fmt != FMT_NONE) out_close();
    if (statspath) write_stats(statspath, N);

    /* ---- summary */
    if (!quiet) {
        fprintf(stderr, "A400000_1T: a(1..%lld) computed in %.1f s (%.2f ns/term)\n", (long long)N, secs, 1e9 * secs / (double)N);
        fprintf(stderr, "  sum  %lld   (A397740(%lld))\n", (long long)sum, (long long)N);
        fprintf(stderr, "  max  %lld = a(%lld); %lld distinct heights; the smallest height not seen is %lld; %d records\n",
                (long long)maxa, (long long)first[maxa], (long long)distinct_heights(), (long long)smallest_unseen(), nrec);
        fprintf(stderr, "  hash %016llx   (FNV-1a over a(1..%lld))\n", (unsigned long long)hash, (long long)N);
        if (memo_levels > 0)
            fprintf(stderr, "  memo: %.3f%% of the terms replayed; level 1: %lld hits, %lld new runs; level 2: %lld hits, %lld new runs;"
                    " %lld evictions; %lld slow steps\n", 100.0 * (double)(m_steps[1] + m_steps[2]) / (double)N,
                    (long long)m_hit[1], (long long)m_miss[1], (long long)m_hit[2], (long long)m_miss[2],
                    (long long)(m_clears[1] + m_clears[2]), (long long)nslow);
        if (directT) fprintf(stderr, "  self-test: a(1..%lld) agree with the direct computation from the definition\n", (long long)directT);
        if (nref_ok) fprintf(stderr, "  %d reference checks passed\n", nref_ok);
    }
    return 0;
}
