CF1296E2.String Coloring (hard version)

This is a hard version of the problem. The actual problems are different, but the easy version is almost a subtask of the hard version. Note that the constraints and the output format are different.

You are given a string $s$ consisting of $n$ lowercase Latin letters.

You have to color all its characters the minimum number of colors (each character to exactly one color, the same letters can be colored the same or different colors, i.e. you can choose exactly one color for each index in $s$).

After coloring, you can swap any two neighboring characters of the string that are colored different colors. You can perform such an operation arbitrary (possibly, zero) number of times.

The goal is to make the string sorted, i.e. all characters should be in alphabetical order.

Your task is to find the minimum number of colors which you have to color the given string in so that after coloring it can become sorted by some sequence of swaps. Note that you have to restore only coloring, not the sequence of swaps.

这是一个该问题的困难版本。实际的问题各不相同，但简单版本几乎是困难版本的一个子任务。请注意，约束条件和输出格式均有所不同。

给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

你需要用最少的颜色数对字符串中所有字符进行染色（每个字符恰好染一种颜色；相同字母可以染相同颜色，也可以染不同颜色，即：对 $s$ 中每个下标，你需恰好选择一种颜色）。

染色完成后，你可以任意次（包括零次）执行如下操作：交换字符串中任意两个相邻字符，但前提是这两个字符的颜色互不相同。

目标是使字符串变为升序排列，即所有字符按字典序非降序排列。

你的任务是求出所需的最少颜色数，使得对给定字符串进行相应染色后，存在某种交换序列可使其变为升序排列。注意：你只需还原染色方案，无需给出具体的交换序列。

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$.

The second line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters.

输入的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示字符串 $s$ 的长度。

输入的第二行包含字符串 $s$，该字符串恰好由 $n$ 个小写拉丁字母组成。

In the first line print one integer $res$ ($1 \le res \le n$) — the minimum number of colors in which you have to color the given string so that after coloring it can become sorted by some sequence of swaps.

In the second line print any possible coloring that can be used to sort the string using some sequence of swaps described in the problem statement. The coloring is the array $c$ of length $n$, where $1 \le c_i \le res$ and $c_i$ means the color of the $i$-th character.

第一行输出一个整数 $res$（$1 \le res \le n$）—— 使得给定字符串在染色后能通过若干次交换操作变为有序的最小颜色数。

第二行输出任意一种可行的染色方案，该方案可配合题目描述中所述的若干次交换操作将字符串排序。染色方案是一个长度为 $n$ 的数组 $c$，其中 $1 \le c_i \le res$，且 $c_i$ 表示第 $i$ 个字符的颜色。