<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

420. Number Permutations
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Two distinct positive integer numbers with decimal notations of the same length are called similar, if their decimal notations can be obtained from each other by permuting the digits.

How many numbers from the segment [l, r] have exactly one similar number in that segment?

Input
The input file contains two integer numbers l and r (1 ≤ l ≤ r ≤ 1015).

Output
Output one integer number — the sought amount.

Example(s)
sample input
sample output
10 99
72

<|response|>
## 1) Abridged problem statement (concise)

Two **distinct** positive integers are **similar** if:

- they have the **same number of digits**, and  
- one can be obtained from the other by **permuting its digits** (no leading zeros allowed because the length must stay the same).

Given \(l, r\) with \(1 \le l \le r \le 10^{15}\), count how many integers \(x \in [l, r]\) have **exactly one** other similar number **also inside** \([l, r]\).

---

## 2) Key observations

### Observation A — Similarity class = “all digit permutations”
For a fixed number \(x\), consider the set \(P(x)\) of all **valid** permutations of its digits (same length ⇒ permutation must not start with zero).  
We need those \(x \in [l,r]\) such that:

\[
|P(x)\cap [l,r]| = 2
\]

(because “exactly one similar number” means exactly two numbers from that permutation class are inside: \(x\) and one more).

---

### Observation B — You only need neighbors in permutation order
Sort all valid digit-permutations of \(x\) increasingly. In that sorted list:

- `prev_perm(x)` = previous permutation (immediately smaller), or “none”
- `next_perm(x)` = next permutation (immediately larger), or “none”

If exactly two permutations of \(x\) lie in \([l,r]\), then for each of those two numbers:

- it has **one neighbor** (prev or next) inside the segment,
- and **no second neighbor** inside (otherwise there would be ≥3 inside).

So for a candidate \(x\), it is enough to check at most 4 values:

- \(p_1 = prev(x)\), \(p_2 = prev(p_1)\)
- \(n_1 = next(x)\), \(n_2 = next(n_1)\)

Then \(x\) has exactly one similar in \([l,r]\) iff:

- either \(p_1 \in [l,r]\) but \(p_2 \notin [l,r]\) and \(n_1 \notin [l,r]\)
- or \(n_1 \in [l,r]\) but \(n_2 \notin [l,r]\) and \(p_1 \notin [l,r]\)

This makes checking a candidate very cheap.

---

### Observation C — We cannot iterate all numbers in \([l,r]\)
The interval may contain up to \(10^{15}\) numbers. We must generate only a **small set of candidates** that could possibly satisfy the “exactly one similar inside” condition.

The provided approach (from the editorial/code) uses a targeted generation of numbers “near” the boundaries \(l\) and \(r\), and also numbers formed by controlled suffix patterns; empirically and by the pruning idea in the editorial comments, **only such numbers can be “cut” by the segment into exactly two permutations**.

---

## 3) Full solution approach

### Step 1 — Implement permutation neighbors
Implement:

- `next_perm(x)`:
  - convert to string
  - apply `next_permutation`
  - if it exists, convert back
  - else return a large sentinel (e.g. \(10^{18}\))

- `prev_perm(x)`:
  - apply `prev_permutation`
  - reject result if it begins with `'0'` (leading zero => shorter length)
  - if none exists, return 0

All numbers here have at most 15 digits, so these operations are fast.

---

### Step 2 — Candidate checker: `has_one_similar(x)`
1. If \(x \notin [l,r]\): false.
2. Compute:
   - `n1 = next_perm(x)`, `n2 = next_perm(n1)`
   - `p1 = prev_perm(x)`, `p2 = prev_perm(p1)`
3. Use the neighbor logic:

- If `p1` is inside: accept iff `p2` is outside and `n1` is outside.
- Else if `n1` is inside: accept iff `n2` is outside.
- Else: reject.

This exactly matches “there is exactly one other permutation inside”.

---

### Step 3 — Generate a manageable candidate set
We generate candidates from both boundaries \(l\) and \(r\).

For each `offset` in `[0..999]` (all possible last-3-digit patterns), and for `base` in `{l, r}`:

1. Add `base`, `prev_perm(base)`, `next_perm(base)` (if they exist).
2. For every digit `d` in `[0..9]`, build suffixes of the form:

- start with `suff = offset`
- repeatedly do `suff = suff*10 + d`

This makes suffixes like: `offsetd`, `offsetdd`, `offsetddd`, ...

For each suffix length, attach it to a prefix of `base` by replacing the last digits:

- maintain `pow10` representing suffix scale
- `pref = base - (base % pow10)`
- `extended = pref + suff`

Add `extended` and also its `prev_perm`/`next_perm` neighbors (because the true answer might be one permutation step away).

Stop extending when `suff > r` (further suffixes only grow).

This yields “tens of thousands” candidates at most.

---

### Step 4 — Count
- Sort + unique candidates.
- For each candidate `x`, if `has_one_similar(x)` is true, increment answer.
- Output answer.

This runs comfortably within limits because:
- candidate count is small,
- each check uses only a few string permutations of length ≤ 15.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t l_val, r_val;
int64_t answer;
vector<int64_t> candidates;

int64_t next_perm(int64_t x) {
    string s = to_string(x);
    if(next_permutation(s.begin(), s.end())) {
        return stoll(s);
    }
    return 1e18;
}

int64_t prev_perm(int64_t x) {
    string s = to_string(x);
    if(prev_permutation(s.begin(), s.end())) {
        if(s[0] == '0') {
            return 0;
        }
        return stoll(s);
    }
    return 0;
}

bool is_inside(int64_t x) { return x >= l_val && x <= r_val; }

bool has_one_similar(int64_t x) {
    if(!is_inside(x)) {
        return false;
    }

    int64_t next1 = next_perm(x);
    int64_t next2 = next_perm(next1);

    int64_t prev1 = prev_perm(x);
    int64_t prev2 = prev_perm(prev1);

    bool has_prev1 = is_inside(prev1);
    bool has_prev2 = is_inside(prev2);
    bool has_next1 = is_inside(next1);
    bool has_next2 = is_inside(next2);

    if(has_prev1) {
        return !has_prev2 && !has_next1;
    }
    if(has_next1) {
        return !has_next2;
    }
    return false;
}

void create_candidates(int64_t base, int64_t offset) {
    if(base < l_val || base > r_val) {
        return;
    }

    candidates.push_back(base);

    int64_t next = next_perm(base);
    if(next < 1e18) {
        candidates.push_back(next);
    }

    int64_t prev = prev_perm(base);
    if(prev > 0) {
        candidates.push_back(prev);
    }

    for(int digit = 0; digit < 10; digit++) {
        int64_t suff = offset;
        int64_t pow10 = 1000;

        for(int len = 0; len < 15; len++) {
            suff = suff * 10 + digit;
            pow10 *= 10;
            if(suff > r_val) {
                break;
            }

            int64_t pref = base - (base % pow10);
            int64_t extended = suff + pref;

            candidates.push_back(extended);

            int64_t next_ext = next_perm(extended);
            if(next_ext < 1e18) {
                candidates.push_back(next_ext);
            }

            int64_t prev_ext = prev_perm(extended);
            if(prev_ext > 0) {
                candidates.push_back(prev_ext);
            }
        }
    }
}

void read() { cin >> l_val >> r_val; }

void solve() {
    // We can make a few observations:
    //
    //     1) A number of the form 100...00 can't be similar.
    //
    //     2) Say we have some l,r and the most significant digit where they
    //        don't agree is i. If 10^i >= 1000 and r_i > l_i + 1, or there is
    //        at least one digit gap between l and r at position i, all the
    //        numbers that disagree with either l_i or r_i at position i can't
    //        be similar, unless all of the digits after i are the same. This
    //        might not be immediately clear, but we have the i >= 3 meaning at
    //        least 3 digits before that that can be permuted in any way. Say we
    //        end with ...abc (a != b != c), then all of the permutations will
    //        also be inside. Even for the case ...baa, we will have the aba and
    //        aab suffix options. The only uncovered option is that all digits
    //        are the same. But there are only (r_i - l_i - 1) * 9 such options.
    //
    //    3) l,r <= 10^15, where this 15 is a bit suspicious. The previous
    //       observation gave us a way to effectively prune the search space
    //       into either agreeing with l_i or r_i, which is two options. Each of
    //       them yields a new l/r of ...0...0 or ...9...9, but more
    //       importantly, we have only 2 branches and we can take them at most
    //       15 times (technically even less). 2^15 is fairly small so this
    //       might be a good direction.
    //
    //    4) We will solve in this recursive way and get candidates. Whenever we
    //       reach the last 3 digits left, we can simply enumerate all numbers
    //       without the pruning. That would be ~1000 candidates in worst case,
    //       and the double decision branching is then only 12. We also
    //       shouldn't forget the additional candidates from point (2).
    //
    //    5) After all of this, we would like to check if all these candidates
    //       are actually similar. One simple approach is to do next_perm(x),
    //       next_perm(next_perm(x)), x, prev_perm(x), prev_perm(prev_perm(x)).
    //       If more than 2 of these are within [l; r] the current candidate is
    //       not similar.
    //
    //    6) We notice that instead of the full recursion, we can combine
    //       arguments 2 and 4 and get that most branches end up being pointless
    //       when we stop matching a prefix of l or r, unless we have <= 3
    //       different characters after that, and we finish with the same
    //       sequence of the same character. This reduces the candidates
    //       significantly, as we can iterate through all 1000 x 10 x 15
    //       possible splits of this sort. We should be careful about these
    //       potentially not including the other numbers in the pair.

    answer = 0;
    candidates.clear();

    for(int64_t delta = 0; delta < 1000; delta++) {
        create_candidates(l_val, delta);
        create_candidates(r_val, delta);
    }

    sort(candidates.begin(), candidates.end());
    candidates.erase(
        unique(candidates.begin(), candidates.end()), candidates.end()
    );

    for(int64_t x: candidates) {
        if(has_one_similar(x)) {
            answer++;
        }
    }

    cout << answer << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

l_val, r_val = map(int, sys.stdin.readline().split())

NO_NEXT = 10**18  # sentinel: no next permutation


def inside(x: int) -> bool:
    return l_val <= x <= r_val


def next_perm(x: int) -> int:
    """
    Return the next larger permutation of digits of x (same length),
    or NO_NEXT if it does not exist.
    """
    s = list(str(x))

    # Find rightmost position i where s[i] < s[i+1]
    i = len(s) - 2
    while i >= 0 and s[i] >= s[i + 1]:
        i -= 1
    if i < 0:
        return NO_NEXT  # already maximum permutation

    # Find rightmost element greater than s[i]
    j = len(s) - 1
    while s[j] <= s[i]:
        j -= 1

    # Swap and reverse suffix
    s[i], s[j] = s[j], s[i]
    s[i + 1:] = reversed(s[i + 1:])
    return int("".join(s))


def prev_perm(x: int) -> int:
    """
    Return the previous smaller permutation of digits of x (same length).
    If it does not exist or leads with zero, return 0.
    """
    if x == 0:
        return 0
    s = list(str(x))

    # Find rightmost position i where s[i] > s[i+1]
    i = len(s) - 2
    while i >= 0 and s[i] <= s[i + 1]:
        i -= 1
    if i < 0:
        return 0  # already minimum permutation

    # Find rightmost element smaller than s[i]
    j = len(s) - 1
    while s[j] >= s[i]:
        j -= 1

    # Swap and reverse suffix
    s[i], s[j] = s[j], s[i]
    s[i + 1:] = reversed(s[i + 1:])

    # Leading zero invalidates the permutation (would change digit length)
    if s[0] == '0':
        return 0

    return int("".join(s))


def has_one_similar(x: int) -> bool:
    """
    Check whether x has exactly one other similar number in [l_val, r_val]
    by examining only its immediate permutation neighbors.
    """
    if not inside(x):
        return False

    n1 = next_perm(x)
    n2 = next_perm(n1) if n1 != NO_NEXT else NO_NEXT

    p1 = prev_perm(x)
    p2 = prev_perm(p1) if p1 != 0 else 0

    in_p1 = inside(p1)
    in_p2 = inside(p2)
    in_n1 = inside(n1)
    in_n2 = inside(n2)

    if in_p1:
        return (not in_p2) and (not in_n1)
    if in_n1:
        return not in_n2
    return False


def create_candidates(base: int, offset: int, out: list[int]) -> None:
    """
    Generate candidates derived from base (l or r) and offset (0..999),
    including neighbors by next/prev permutation.
    """
    if not inside(base):
        return

    out.append(base)

    nb = next_perm(base)
    if nb != NO_NEXT:
        out.append(nb)

    pb = prev_perm(base)
    if pb != 0:
        out.append(pb)

    for d in range(10):
        suff = offset
        pow10 = 1000

        for _ in range(15):
            suff = suff * 10 + d
            pow10 *= 10

            if suff > r_val:
                break

            pref = base - (base % pow10)
            x = pref + suff

            out.append(x)

            nx = next_perm(x)
            if nx != NO_NEXT:
                out.append(nx)

            px = prev_perm(x)
            if px != 0:
                out.append(px)


# Build candidate list
cands = []
for offset in range(1000):
    create_candidates(l_val, offset, cands)
    create_candidates(r_val, offset, cands)

# Deduplicate
cands = sorted(set(cands))

# Count
ans = 0
for x in cands:
    if has_one_similar(x):
        ans += 1

print(ans)
```

---

If you want, I can also add a short proof sketch for why checking only `(prev, prevprev, next, nextnext)` is sufficient, and/or discuss why the candidate generation focuses on “boundary-structured” numbers.