// 演算法 / Algorithm:
// 1) 區間拆分 / Range split: answer = f(num2) - f(num1-1), where f(N) = total
//    waviness over [0, N].
// 2) 數位 DP / Digit DP: build numbers MSB->LSB, state (pos, last, secondLast,
//    tight). When we place digit d, we judge whether `last` became a peak/valley
//    using (secondLast, last, d). Each state returns (count, sum) so we can sum
//    waviness, not just count numbers.

#include <string.h>   // 為了 memset 清空記憶化陣列 / for memset to clear memo

typedef long long ll; // 取別名，數值最大約 1.4e16 需要 64 位元 / 64-bit alias

// 記憶化陣列：索引為 [pos][last][secondLast]；last/secondLast 取 0..10（10 是哨兵）
// memo arrays indexed by [pos][last][secondLast]; values 0..10 (10 = sentinel)
static ll  cntMemo[16][11][11];  // 該狀態能形成的數字個數 / count of numbers
static ll  sumMemo[16][11][11];  // 該狀態累積的波動度總和 / accumulated waviness
static char vis[16][11][11];     // 該狀態是否已算過 / has this state been computed
static int dig[16];              // 上界 N 的每一位（最高位在 dig[0]）/ digits of N, MSB first
static int ndig;                 // N 的位數 / number of digits in N

// dp 透過指標回傳兩個值 cnt 與 sum / dp returns two values via pointers
// pos: 目前要填的位置 / current position to fill
// last: 上一個真實數位（10 表示還沒有真位）/ previous real digit (10 = none yet)
// sec : 上上個真實數位（10 表示不足兩位）/ digit before last (10 = fewer than two)
// tight: 前綴是否仍緊貼 N / is the prefix still equal to N's prefix
static void dp(int pos, int last, int sec, int tight, ll *cnt, ll *sum) {
    if (pos == ndig) {        // 已填完所有位，形成一個完整數字 / a full number formed
        *cnt = 1;             // 這是一個數字 / it is exactly one number
        *sum = 0;             // 它在此處不再新增波動度 / no further waviness here
        return;
    }
    // 非 tight 且算過 → 直接取快取 / if free (not tight) and cached, reuse it
    if (!tight && vis[pos][last][sec]) {
        *cnt = cntMemo[pos][last][sec];
        *sum = sumMemo[pos][last][sec];
        return;
    }

    int hi = tight ? dig[pos] : 9;  // tight 時這位最多放到 dig[pos]，否則放到 9
                                    // upper bound for this digit
    ll tc = 0, ts = 0;              // 本狀態累計的 count 與 sum / running totals

    for (int d = 0; d <= hi; d++) { // 嘗試這位放 0..hi 的每個數字 / try each digit d
        int nlast, nsec;            // 放完之後的新 last/secondLast / next state's digits
        ll e = 0;                   // 這步是否新增一個峰/谷（0 或 1）/ peak/valley gained

        if (last == 10) {           // 還在前導零階段 / still in the leading-zero phase
            if (d == 0) {           // 又放一個前導零 / another leading zero
                nlast = 10; nsec = 10;   // 仍視為「尚無真位」/ still "no real digit"
            } else {                // 第一個非零數位出現 / first nonzero digit appears
                nlast = d; nsec = 10;    // 它是最高位，前面沒有鄰居 / it's the MSD
            }
        } else {                    // 已有真實數位 / at least one real digit exists
            nsec = last;            // 舊的 last 變成新的 secondLast / shift left
            nlast = d;              // 新放下的 d 變成新的 last / d becomes last
            if (sec != 10) {        // 必須左右都有真鄰居才可能是峰/谷 / need both neighbors
                // last 的左鄰是 sec、右鄰是 d / last's neighbors are sec and d
                if ((last > sec && last > d) ||   // 比兩邊都大 → 山峰 / strictly greater = peak
                    (last < sec && last < d)) {   // 比兩邊都小 → 山谷 / strictly smaller = valley
                    e = 1;          // 這個數字此位多 1 波動度 / +1 waviness for this number
                }
            }
        }

        ll c, s;                    // 遞迴取得子問題的 (count, sum) / child results
        // tight 只有在這位剛好放到上界 d==hi 時才會延續 / stay tight only when d==hi
        dp(pos + 1, nlast, nsec, tight && (d == hi), &c, &s);

        tc += c;                    // 累加數字個數 / accumulate count
        ts += s + e * c;            // 子總和 + 本步每個數字各加 e / childSum + e per number
    }

    if (!tight) {                   // 只有非 tight 狀態能安全快取 / only free states are reusable
        vis[pos][last][sec] = 1;
        cntMemo[pos][last][sec] = tc;
        sumMemo[pos][last][sec] = ts;
    }
    *cnt = tc;                      // 透過指標把結果回傳 / hand results back via pointers
    *sum = ts;
}

// 計算 [0, N] 的波動度總和 / total waviness over [0, N]
static ll f(ll N) {
    if (N < 0) return 0;            // num1 可能為 1，N=num1-1 可能為 0；負數視為空 / guard

    int tmp[20], tn = 0;            // 暫存 N 的各位（最低位先取出）/ digits, LSB first
    if (N == 0) {                   // N==0 要特別處理，否則下方迴圈跑不到 / handle zero
        tmp[tn++] = 0;
    }
    ll t = N;
    while (t > 0) {                 // 反覆取餘數拆出每一位 / peel off digits by %10 and /10
        tmp[tn++] = (int)(t % 10);
        t /= 10;
    }
    ndig = tn;
    for (int i = 0; i < tn; i++)    // 反轉成最高位在前 / reverse so MSD is dig[0]
        dig[i] = tmp[tn - 1 - i];

    memset(vis, 0, sizeof(vis));    // 每次 f 都重置快取（位數可能不同）/ reset cache each call

    ll c, s;
    dp(0, 10, 10, 1, &c, &s);       // 從最高位開始，last/sec 皆為哨兵、tight=1 / start state
    return s;                       // 我們要的是波動度總和 / we want the sum
}

// LeetCode 入口函式 / entry point
long long totalWaviness(long long num1, long long num2) {
    return f(num2) - f(num1 - 1);   // 區間 = 上界前綴和 - 下界前綴和 / prefix-sum subtraction
}