import java.util.*;
public class Solution {
    public static int search(int[] nums,int cur){
        int l = 0;
        int r = nums.length;
        while(l<r){
            int mid = l + (r-l)/2;
            if(nums[mid]<cur)
                l=mid+1;
            else
                r = mid;
        }
        return l;
    }
    public static int getMaxN(int[]nums,int n){
        // 1 2 4 9          2499
        String target = String.valueOf(n);
        //若高位满足条件，则低位全取最大值
        boolean flag = false;
        StringBuilder sb = new StringBuilder();
        Arrays.sort(nums);
        //记录target中每一位在nums中的位置，方便后续搜索
        int maxPosition = 0;

        for(int i=0;i<target.length();i++){
            if(flag){
                sb.append(nums[nums.length-1]);
                continue;
            }
            int cur = target.charAt(i)-'0';
            int tmp = search(nums,cur);

            if(tmp>=nums.length||nums[tmp]>cur){
                if(tmp==0)break;
                sb.append(nums[tmp-1]);
                flag = true;
            }
            else {
                sb.append(nums[tmp]);
                if(nums[tmp]<cur)flag = true;
            }
        }
        //长度相等，且非等值，直接返回结果
        if(sb.length()==target.length()&&flag)return Integer.valueOf(sb.toString());
        //排除相等的情况
        flag = false;
        if(sb.length()==target.length()){
            for(int i=target.length()-1;i>=0;i--){
                maxPosition = search(nums,target.charAt(i)-'0');
                if(maxPosition>0){
                    sb.replace(i,i+1,String.valueOf(nums[maxPosition-1]));
                    flag = true;
                    break;
                }
                else{
                    sb.replace(i,i+1,String.valueOf(nums[nums.length-1]));
                }
            }
        }
        if(flag)return Integer.valueOf(sb.toString());
        sb = new StringBuilder();
        for(int i=0;i<target.length()-1;i++){
                sb.append(nums[nums.length-1]);
        }


        return sb.length()>0?Integer.valueOf(sb.toString()):0;

    }

    public static void main(String[] args) {

        System.out.println(Solution.getMaxN(new int[]{1, 2, 9, 4},2533));
        System.out.println(Solution.getMaxN(new int[]{1, 2, 5, 4},2543));
        System.out.println(Solution.getMaxN(new int[]{1, 2, 5, 4},2541));
        System.out.println(Solution.getMaxN(new int[]{1, 2, 9, 4},2111));
        System.out.println(Solution.getMaxN(new int[]{5, 9},5555));
        System.out.println(Solution.getMaxN(new int[]{1},1));


    }
}