import java.util.*; public class Euler328 { static int depthInt(int m) { if (m <= 0) return -1; return 31 - Integer.numberOfLeadingZeros(m); } static class BandRMQ { int d; int start; int end; int len; long[] s1; long[] s2; int[] lg; int[][] st1; int[][] st2; void build(int d_, int start_, int end_, long[] A, long[] B) { d = d_; start = start_; end = end_; len = end - start + 1; s1 = new long[len]; s2 = new long[len]; for (int i = 0; i < len; i++) { int m = start + i; s1[i] = A[m] - 1L * m * (d + 1); s2[i] = B[m] - 1L * m * d; } lg = new int[len + 1]; for (int i = 2; i <= len; i++) lg[i] = lg[i / 2] + 1; int K = lg[len] + 1; st1 = new int[K][len]; st2 = new int[K][len]; for (int i = 0; i < len; i++) { st1[0][i] = i; st2[0][i] = i; } for (int k = 1; k < K; k++) { int span = 1 << (k - 1); int limit = len - (1 << k) + 1; for (int i = 0; i < limit; i++) { int i1 = st1[k - 1][i]; int i2 = st1[k - 1][i + span]; st1[k][i] = (s1[i1] <= s1[i2]) ? i1 : i2; int j1 = st2[k - 1][i]; int j2 = st2[k - 1][i + span]; st2[k][i] = (s2[j1] <= s2[j2]) ? j1 : j2; } } } int rmqArgMin1Abs(int lAbs, int rAbs) { int l = lAbs - start; int r = rAbs - start; int L = r - l + 1; int k = lg[L]; int i1 = st1[k][l]; int i2 = st1[k][r - (1 << k) + 1]; int idx = (s1[i1] <= s1[i2]) ? i1 : i2; return start + idx; } int rmqArgMin2Abs(int lAbs, int rAbs) { int l = lAbs - start; int r = rAbs - start; int L = r - l + 1; int k = lg[L]; int i1 = st2[k][l]; int i2 = st2[k][r - (1 << k) + 1]; int idx = (s2[i1] <= s2[i2]) ? i1 : i2; return start + idx; } } public static String solve() { int N = 200000; long INF = 1L << 62; int maxD = depthInt(N); long[] A = new long[N + 1]; long[] B = new long[N + 1]; long[][] sufMinVal = new long[maxD + 1][]; int[][] sufArgVal = new int[maxD + 1][]; boolean[] built = new boolean[maxD + 1]; built[0] = true; for (int m = 2; m <= N; m++) { int d = depthInt(m); if (d >= 1 && !built[d]) { int lo = 1 << (d - 1); int hi = (1 << d) - 1; int len = hi - lo + 1; sufMinVal[d] = new long[len]; sufArgVal[d] = new int[len]; long best = A[hi] - 1L * hi * d; int arg = hi; sufMinVal[d][len - 1] = best; sufArgVal[d][len - 1] = arg; for (int i = len - 2; i >= 0; i--) { int q = lo + i; long v = A[q] - 1L * q * d; if (v < best) { best = v; arg = q; } sufMinVal[d][i] = best; sufArgVal[d][i] = arg; } built[d] = true; } if (d == 0) { A[m] = 0; continue; } int base = 1 << (d - 1); int qLo = Math.max(base, m - (1 << d)); long rightCost = 1L * m * d + sufMinVal[d][qLo - base]; long leftCost = INF; int p = m - base + 1; if (p <= (1 << d)) { leftCost = 1L * p + A[p - 1]; } A[m] = Math.min(leftCost, rightCost); } for (int d = 1; d <= maxD; d++) { if (!built[d]) { int lo = 1 << (d - 1); int hi = (1 << d) - 1; int len = hi - lo + 1; sufMinVal[d] = new long[len]; sufArgVal[d] = new int[len]; long best = A[hi] - 1L * hi * d; int arg = hi; sufMinVal[d][len - 1] = best; sufArgVal[d][len - 1] = arg; for (int i = len - 2; i >= 0; i--) { int q = lo + i; long v = A[q] - 1L * q * d; if (v < best) { best = v; arg = q; } sufMinVal[d][i] = best; sufArgVal[d][i] = arg; } built[d] = true; } } for (int m = 2; m <= N; m++) { int d = depthInt(m); if (d == 0) { B[m] = 0; continue; } int base = 1 << (d - 1); int p0 = m - base + 1; long leftA = INF; if (p0 <= (1 << d)) { leftA = 1L * p0 + A[p0 - 1]; } int qLo = Math.max(base, m - (1 << d)); long rightBestA = 1L * m * d + sufMinVal[d][qLo - base]; if (leftA == A[m]) { int L = p0 - 1; int R = m - p0; long bestB = Math.max(1L * p0 + B[L], 1L * p0 * (d - 1) + A[R]); if (rightBestA == A[m]) { int q = sufArgVal[d][qLo - base]; long cand = 1L * (m - q) * (d - 1) + B[q]; int L2 = m - q - 1; int Dl = depthInt(L2); if (Dl == d - 1) cand = Math.max(cand, 1L * (m - q) + B[L2]); else if (Dl == d - 2) cand = Math.max(cand, 1L * (m - q) + A[L2]); bestB = Math.min(bestB, cand); } B[m] = bestB; } else { int q = sufArgVal[d][qLo - base]; long cand = 1L * (m - q) * (d - 1) + B[q]; int L2 = m - q - 1; int Dl = depthInt(L2); if (Dl == d - 1) cand = Math.max(cand, 1L * (m - q) + B[L2]); else if (Dl == d - 2) cand = Math.max(cand, 1L * (m - q) + A[L2]); B[m] = cand; } } BandRMQ[] bands = new BandRMQ[maxD + 1]; boolean[] hasBand = new boolean[maxD + 1]; for (int d = 1; d <= maxD; d++) { bands[d] = new BandRMQ(); int start = 1 << d; int end = Math.min((1 << (d + 1)) - 1, N); if (start <= end) { bands[d].build(d, start, end, A, B); hasBand[d] = true; } } long[] C = new long[N + 1]; long sum = 0; for (int n = 2; n <= N; n++) { long best = INF; int m1 = 1; int k1 = n - m1; long cand1 = 1L * k1 + C[k1 - 1]; best = Math.min(best, cand1); int maxDn = depthInt(n - 1); for (int d = 1; d <= maxDn; d++) { int mLo = 1 << d; int mHi = Math.min((1 << (d + 1)) - 1, n - 1); if (mLo > mHi) continue; boolean pHi = C[n - mHi - 1] <= Math.max(1L * (n - mHi) * d + A[mHi], 1L * (n - mHi) * (d - 1) + B[mHi]); if (!pHi) { for (int m : new int[] { mHi, mHi - 1 }) { if (m < mLo || m > mHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } continue; } int mP; boolean pLo = C[n - mLo - 1] <= Math.max(1L * (n - mLo) * d + A[mLo], 1L * (n - mLo) * (d - 1) + B[mLo]); if (pLo) { mP = mLo; } else { int lo = mLo, hi = mHi; while (lo < hi) { int mid = (lo + hi) >> 1; boolean pMid = C[n - mid - 1] <= Math.max(1L * (n - mid) * d + A[mid], 1L * (n - mid) * (d - 1) + B[mid]); if (pMid) hi = mid; else lo = mid + 1; } mP = lo; for (int m : new int[] { mP - 1, mP }) { if (m < mLo || m > mHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } } int subLo = mP; int subHi = mHi; for (int m : new int[] { subLo, subHi, subHi - 1, subHi - 2 }) { if (m < subLo || m > subHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } long hLo = 1L * (n - subLo) + A[subLo] - B[subLo]; long hHi = 1L * (n - subHi) + A[subHi] - B[subHi]; if (hasBand[d]) { BandRMQ band = bands[d]; if (hLo >= 0 && hHi >= 0) { int mMin = band.rmqArgMin1Abs(subLo, subHi); for (int m = mMin - 2; m <= mMin + 2; m++) { if (m < subLo || m > subHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } } else if (hLo <= 0 && hHi <= 0) { int mMin = band.rmqArgMin2Abs(subLo, subHi); for (int m = mMin - 2; m <= mMin + 2; m++) { if (m < subLo || m > subHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } } else { int lo = subLo, hi = subHi; while (lo < hi) { int mid = (lo + hi) >> 1; long hMid = 1L * (n - mid) + A[mid] - B[mid]; if (hMid >= 0) hi = mid; else lo = mid + 1; } int mQ = lo; for (int m = mQ - 4; m <= mQ + 4; m++) { if (m < subLo || m > subHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } int mMin1 = band.rmqArgMin1Abs(subLo, subHi); int mMin2 = band.rmqArgMin2Abs(subLo, subHi); for (int mm : new int[] { mMin1, mMin2 }) { for (int m = mm - 2; m <= mm + 2; m++) { if (m < subLo || m > subHi) continue; int k = n - m; long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m])); best = Math.min(best, cand); } } } } } C[n] = best; sum += best; } return String.valueOf(sum); } public static void main(String[] args) { System.out.println(solve()); } }