<|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;

static const int64_t NO_NEXT = (int64_t)1e18; // sentinel: no next permutation

int64_t l_val, r_val;
vector<int64_t> candidates;

// Return true if x is inside [l_val, r_val]
static inline bool inside(int64_t x) {
    return l_val <= x && x <= r_val;
}

// Next larger digit permutation of x (same length).
// If it does not exist, return NO_NEXT.
int64_t next_perm(int64_t x) {
    string s = to_string(x);
    if (next_permutation(s.begin(), s.end())) {
        return stoll(s);
    }
    return NO_NEXT;
}

// Previous smaller digit permutation of x (same length).
// If it does not exist, return 0.
// If it leads with '0', it's invalid (would reduce digit length), return 0.
int64_t prev_perm(int64_t x) {
    if (x == 0) return 0;
    string s = to_string(x);
    if (prev_permutation(s.begin(), s.end())) {
        if (s[0] == '0') return 0;
        return stoll(s);
    }
    return 0;
}

// Check if x has exactly ONE other similar number in [l_val, r_val].
// Uses only immediate neighbors among permutations.
bool has_one_similar(int64_t x) {
    if (!inside(x)) return false;

    int64_t n1 = next_perm(x);
    int64_t n2 = (n1 == NO_NEXT ? NO_NEXT : next_perm(n1));

    int64_t p1 = prev_perm(x);
    int64_t p2 = (p1 == 0 ? 0 : prev_perm(p1));

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

    // If previous permutation is inside, it must be the only other one:
    // - no second below (p2 outside) and none above (n1 outside).
    if (in_p1) return !in_p2 && !in_n1;

    // Otherwise, if next permutation is inside, it must be the only other one:
    // - next-next must be outside.
    if (in_n1) return !in_n2;

    return false;
}

// Generate candidate numbers derived from "base" (either l or r) and "offset" (0..999).
// Adds base itself, its neighbor permutations, and numbers formed by:
//   prefix of base + (offset followed by repeated digit d).
void create_candidates(int64_t base, int64_t offset) {
    if (!inside(base)) return;

    // base and its immediate perm-neighbors
    candidates.push_back(base);

    int64_t nb = next_perm(base);
    if (nb != NO_NEXT) candidates.push_back(nb);

    int64_t pb = prev_perm(base);
    if (pb != 0) candidates.push_back(pb);

    // Now build many "controlled suffix" numbers
    for (int d = 0; d <= 9; d++) {
        int64_t suff = offset;  // starts with 0..999
        int64_t pow10 = 1000;   // suffix currently conceptually has 3 digits (offset)

        // Extend suffix up to 15 times (numbers <= 1e15 => at most 16 digits,
        // but 15 is enough for our generation; also stops early by suff > r_val).
        for (int len = 0; len < 15; len++) {
            // append digit d to the suffix
            suff = suff * 10 + d;
            pow10 *= 10;

            // if suffix already exceeds r, longer suffix will only be larger
            if (suff > r_val) break;

            // take prefix of base by clearing last digits (those covered by pow10)
            int64_t pref = base - (base % pow10);
            int64_t x = pref + suff;

            candidates.push_back(x);

            // include neighbors: the actual “good” number may be one perm step away
            int64_t nx = next_perm(x);
            if (nx != NO_NEXT) candidates.push_back(nx);

            int64_t px = prev_perm(x);
            if (px != 0) candidates.push_back(px);
        }
    }
}

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

    cin >> l_val >> r_val;

    // Generate candidates from both ends for all offsets 0..999
    for (int64_t offset = 0; offset < 1000; offset++) {
        create_candidates(l_val, offset);
        create_candidates(r_val, offset);
    }

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

    // Count how many candidates satisfy the property
    int64_t ans = 0;
    for (int64_t x : candidates) {
        if (has_one_similar(x)) ans++;
    }

    cout << ans << "\n";
    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.