A96428.插入一位数字

给定一个长度为 $n$ 的十进制数字串 $s$（表示一个非负整数，允许 $s=0$），以及一个数字 $d$（$0\le d\le 9$）。你需要将数字 $d$ 恰好插入一次到 $s$ 的某个位置（可以在最前面或最后面），使得得到的新数字尽可能大。输出这个新数字对应的字符串。

插入规则等价于：从左到右扫描 $s$，找到第一个满足 $s_i \lt d$ 的位置，把 $d$ 插入到该位置之前；如果不存在这样的 $i$，则将 $d$ 追加到末尾。

第一行：一个整数 $n$（$1\le n\le 2\times 10^5$），表示字符串 $s$ 的长度。

第二行：一个仅由字符 '0'–'9' 组成的字符串 $s$，长度为 $n$。当 $n>1$ 时，$s$ 无前导零。

第三行：一个字符 $d$，为 '0'–'9' 之一。

输出将 $d$ 插入一次后得到的、数值最大的字符串。

$1\le n\le 2\times 10^5$