You are given a very large integer n, represented as a string,​​​​​​ and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximize n's numerical value by inserting x anywhere in the decimal representation of n​​​​​​. You cannot insert x to the left of the negative sign.


	For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
	If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.


Return a string representing the maximum value of n​​​​​​ after the insertion.

&nbsp;
Example 1:

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.


Example 2:

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.


&nbsp;
Constraints:


	1 &lt;= n.length &lt;= 105
	1 &lt;= x &lt;= 9
	The digits in n​​​ are in the range [1, 9].
	n is a valid representation of an integer.
	In the case of a negative n,​​​​​​ it will begin with '-'.


class Solution:
    def maxValue(self, n: str, x: int) -> str:
        if int(n)>0:
            ans = ""
            flag = False
            for i in range(len(n)):
                if int(n[i])>=x:
                    ans += n[i]
                else:
                    a = n[:i]
                    b = n[i:]
                    ans = a+str(x)+b
                
                    flag = True
                    break
            if not flag:
                ans += str(x)
        else:
            n = n[1:]
            ans = ""
            flag = False
            for i in range(len(n)):
                if int(n[i])<=x:
                    ans += n[i]
                else:
                    a = n[:i]
                    b = n[i:]
                    ans = a+str(x)+b
            
                    flag = True
                    break
            if not flag:
                ans += str(x)
            ans = "-"+ans
        
        return ans
                    
class Solution {
    public String maxValue(String n, int x) {
        StringBuilder res= new StringBuilder();
        int i=0, j=0;
        if(n.charAt(0)=='-'){
            res.append(n.charAt(0));
            for(j=1; j<n.length(); j++){
               char ch= n.charAt(j);
               int val= ch-'0';
               if(val<= x){  
                  res.append(ch);
               }else{
                   res.append(x);
                   res.append(ch);
                   res.append(n.substring(j+1));
                   break;
               }
           }
            if(j==n.length()){
                res.append(x);
            }
        }
        else{
            for(i=0; i<n.length(); i++){
               char ch= n.charAt(i);
               int val= ch-'0';
                
               if(val>= x){  
                  res.append(ch);
               }else{
                   res.append(x);
                   res.append(ch);
                   res.append(n.substring(i+1));
                   break;
               }
           }
            if(i==n.length()){
                res.append(x);
            }
        }
        return res.toString();
    }
}
class Solution { 

public:
string maxValue(string s, int x) {
    int p=0,flag=0;
    char ch='0'+x;  //change int to char
    string str;
	
    if(s[0]=='-')
    {   //for negative numbers
	     for(int i=1;i<s.size();i++)
        {
          if(ch<s[i] && !flag){
            str+=ch;
            str+=s[i];
            flag=1; 
          }
          else 
           str+=s[i];
        }
        if(!flag) str+=ch;
        return '-'+str;
    }
    
	// if number is positive
    for(int i=0;i<s.size();i++)
    {
       if(ch>s[i] && !flag){
         str+=ch;
         str+=s[i];
         flag=1;
       }
       else 
        str+=s[i];
    }    
    if(!flag) str+=ch;
    return str;
  }
};
var maxValue = function(n, x) {
    let i;

    // if the number if positive, find the first
    // number that is less than x
    if (n[0] !== '-') {
        for (i = 0; i < n.length; i++) {
            if (Number(n[i]) < x) break;
        }        
    
    // if the number is negative, find the first
    // number that is greater than x
    } else {
        for (i = 1; i < n.length; i++) {
            if (Number(n[i]) > x) break;
        }
    }
    
    // return the string with x inserted at the found index
    return n.slice(0, i) + x + n.slice(i)
};


///////////////// short hand ////////////////////


var maxValue = function(n, x) {
    let i;
    if (n[0] !== '-') {
        for (i = 0; i < n.length; i++) {
            if (Number(n[i]) < x) break;
        }        
    } else {
        for (i = 1; i < n.length; i++) {
            if (Number(n[i]) > x) break;
        }
    }
    return n.slice(0, i) + x + n.slice(i)
};
Maximum Value after Insertion