def int_to_roman(n):
    if not isinstance(n, int) or not (1 <= n <= 3999):
        raise ValueError("Integer must be in range 1..3999")
    
    values = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
        (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
    ]
    
    result = []
    for value, symbol in values:
        while n >= value:
            result.append(symbol)
            n -= value
    return "".join(result)


def roman_to_int(s):
    if not s:
        raise ValueError("Empty string is not a valid Roman numeral")
    
    # Map of single symbols to values
    single_values = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
    
    # Valid subtractive pairs
    subtractive_pairs = {
        'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900
    }
    
    # Check for invalid characters
    for char in s:
        if char not in single_values:
            raise ValueError(f"Invalid character in Roman numeral: {char}")
    
    result = 0
    i = 0
    n = len(s)
    
    # Track what was last added to enforce non-increasing order of "blocks"
    # and to detect non-canonical forms
    last_value = float('inf')
    
    while i < n:
        # Try to match a subtractive pair first
        if i + 1 < n:
            pair = s[i:i+2]
            if pair in subtractive_pairs:
                # Check for non-canonical: pairs like "VX", "LC", "DM" are invalid
                # Also check ordering: we shouldn't have a larger or equal value before
                pair_value = subtractive_pairs[pair]
                if pair_value >= last_value:
                    raise ValueError("Non-canonical Roman numeral: invalid ordering")
                result += pair_value
                last_value = pair_value
                i += 2
                continue
        
        # Single symbol
        symbol = s[i]
        value = single_values[symbol]
        
        # Check ordering: symbols must generally be non-increasing
        # But we need to be careful: V, L, D can only appear once and can't be subtracted from
        if value >= last_value:
            # Same symbol repeated is only allowed for I, X, C, M (up to 3 times)
            if value == last_value:
                # Check if we're about to make a 4-repeat (already had same, and this is same)
                # Actually we need to check the run length
                pass  # Will check below with context
            else:
                raise ValueError("Non-canonical Roman numeral: invalid ordering")
        
        # Check for more than 3 repeats of I, X, C, M
        # Check for repeats of V, L, D
        # We need to look ahead and behind to check runs
        
        result += value
        last_value = value
        i += 1
    
    # Verify the result by re-parsing more strictly
    # Let's do a full validation pass
    
    # Check for invalid patterns: more than 3 in a row, V/L/D repeated, invalid subtractive
    # Re-parse with stricter checks
    
    # Validate by trying to match canonical patterns strictly
    _validate_roman(s)
    
    return result


def _validate_roman(s):
    """Strict validation of canonical Roman numerals."""
    if not s:
        raise ValueError("Empty string")
    
    # Valid symbols
    valid_chars = set('IVXLCDM')
    if not set(s).issubset(valid_chars):
        raise ValueError("Invalid characters")
    
    # Check for repeated V, L, or D
    for char in 'VLD':
        if s.count(char) > 1:
            raise ValueError(f"Non-canonical: repeated {char}")
    
    # Check for more than 3 consecutive identical symbols
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        run_length = j - i
        if run_length > 3 and s[i] in 'IXCM':
            raise ValueError(f"Non-canonical: more than 3 consecutive {s[i]}")
        elif run_length > 1 and s[i] in 'VLD':
            raise ValueError(f"Non-canonical: repeated {s[i]}")
        i = j
    
    # Now parse and verify structure
    # Use a state machine / greedy approach matching canonical forms
    
    # Define valid patterns in order
    patterns = [
        ('M', 1000), ('CM', 900), ('D', 500), ('CD', 400),
        ('C', 100), ('XC', 90), ('L', 50), ('XL', 40),
        ('X', 10), ('IX', 9), ('V', 5), ('IV', 4), ('I', 1)
    ]
    
    pos = 0
    last_matched_value = float('inf')
    
    while pos < len(s):
        matched = False
        for pattern, value in patterns:
            if s.startswith(pattern, pos):
                # Check ordering: must be strictly decreasing value (or equal for repeats)
                if value > last_matched_value:
                    raise ValueError("Non-canonical: invalid ordering")
                # For subtractive pairs, ensure we don't have invalid preceding context
                if pattern in ('CM', 'CD', 'XC', 'XL', 'IX', 'IV'):
                    # These are already valid; check that previous wasn't same or larger
                    if value >= last_matched_value and last_matched_value != float('inf'):
                        # Actually this is fine if last was larger, but we need strict
                        pass
                pos += len(pattern)
                last_matched_value = value
                matched = True
                break
        
        if not matched:
            raise ValueError("Non-canonical: invalid pattern")
    
    # Additional check: verify no ambiguous patterns like "IIX", "VX", etc.
    # The greedy parse above should catch most, but let's verify with a regex-like check
    
    # Check specific invalid patterns
    invalid_substrings = ['IIII', 'VV', 'LL', 'DD', 'XXXX', 'CCCC', 'MMMM',
                          'IL', 'IC', 'ID', 'IM', 'VX', 'VC', 'VD', 'VM',
                          'LC', 'LD', 'LM', 'XD', 'XM', 'DM']
    for bad in invalid_substrings:
        if bad in s:
            raise ValueError(f"Non-canonical: contains {bad}")
    
    # Verify the total value is in range
    total = 0
    i = 0
    while i < len(s):
        if i + 1 < len(s) and s[i:i+2] in {'CM': 900, 'CD': 400, 'XC': 90, 'XL': 40, 'IX': 9, 'IV': 4}:
            total += {'CM': 900, 'CD': 400, 'XC': 90, 'XL': 40, 'IX': 9, 'IV': 4}[s[i:i+2]]
            i += 2
        else:
            total += {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}[s[i]]
            i += 1
    
    if not (1 <= total <= 3999):
        raise ValueError("Value out of range")


def roman_to_int(s):
    if not s:
        raise ValueError("Empty string is not a valid Roman numeral")
    
    # Validate strict canonical form
    _validate_roman(s)
    
    # Now compute the value
    subtractive_pairs = {'CM': 900, 'CD': 400, 'XC': 90, 'XL': 40, 'IX': 9, 'IV': 4}
    single_values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    
    result = 0
    i = 0
    while i < len(s):
        if i + 1 < len(s) and s[i:i+2] in subtractive_pairs:
            result += subtractive_pairs[s[i:i+2]]
            i += 2
        else:
            result += single_values[s[i]]
            i += 1
    
    return result