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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
9
abacbecfd

Output
2
1 1 2 1 2 1 2 1 2 

Input
8
aaabbcbb

Output
2
1 2 1 2 1 2 1 1

Input
7
abcdedc

Output
3
1 1 1 1 1 2 3 

Input
5
abcde

Output
1
1 1 1 1 1

Difficulty: introductory

Starter code:

Solutions:

alp = "abcdefghijklmnopqrstuvwxyz"

dic = {}
for i,s in enumerate(alp):
    dic[s] = i

lis = [0] * 27

n = int(input())
S = input()
ans = []

for i,s in enumerate(S):

    ind = dic[s]

    ans.append(max(lis[ind+1:]) + 1)

    lis[ind] = ans[-1]

print(max(ans))
print(" ".join(map(str,ans)))


n = int(input())
s = input()
f = [0 for _ in range(26)]
res = [1 for _ in range(n)]
for i in range(n):
    c = ord(s[i]) - ord('a')
    for j in range(c + 1, 26):
        res[i] = max(res[i], f[j] + 1)
    f[c] = max(f[c], res[i])
    
maxres = max(res)
print(maxres)
for i in res:
    print(i, end = ' ')

from math import *
n = int(input())
s = input()
pre = [0 for i in range(n)]
pre[0] = 1
prev = s[0]
lst = [-1 for i in range(26)]
lst[0] = s[0]
ct = 1
for i in range(1,n):
	for j in range(26):
		if(lst[j] == -1 or lst[j] <= s[i]):
			lst[j] = s[i]
			pre[i] = j+1
			ct = max(ct,j+1)
			break

print(ct)
for i in pre:
	print(i,end = " ")


n = int(input())
a = list([ord(c)-97 for c in input()])
color = [0]*26
ans = [0]*n
last = -1

for i, c in enumerate(a):
    col = 0
    if last <= c:
        last = c
        if color[c] == 0:
            col = 1
        else:
            col = color[c] & (-color[c])
    else:
        col = 1
        for j in range(last, c, -1):
            while col & color[j]:
                col <<= 1

    color[c] |= col
    ans[i] = len(bin(col)) - 2

print(max(ans))
print(*ans)


#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, a):
        # Operator
        self.op = lambda a, b : max(a, b)
        # Identity element
        self.e = 0 

        self.n = len(a)
        self.lv = (self.n - 1).bit_length()
        self.size = 2**self.lv
        self.data = [self.e] * (2*self.size - 1)
        # Bisect checking function 
        self._check = lambda x, acc : acc >= x
        self._acc = self.e

        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = self.op(self.data[i*2 + 1], self.data[i*2 + 2])

    # Update ak as x (0-indexed)
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r) (0-indexed)
    def fold(self, l, r):
        L = l + self.size; R = r + self.size
        s = self.e
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.data[R-1])
            if L & 1:
                s = self.op(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def _bisect_forward(self, x, start, k):
        # When segment-k is at the bottom, accumulate and return.
        if k >= self.size - 1:
            self._acc = self.op(self._acc, self.data[k])
            if self._check(x, self._acc):
                return k - (self.size - 1)
            else:
                return -1
        width = 2**(self.lv - (k+1).bit_length() + 1)
        mid = (k+1) * width + width // 2 - self.size 
        # When left-child isn't in range, just look at right-child. 
        if mid <= start:
            return self._bisect_forward(x, start, 2*k + 2)
        # When segment-k is in range and has no answer in it, accumulate and return -1
        tmp_acc = self.op(self._acc, self.data[k])
        if start <= mid - width // 2 and not self._check(x, tmp_acc):
            self._acc = tmp_acc
            return -1
        # Check left-child then right-child
        vl = self._bisect_forward(x, start, 2*k + 1)
        if vl != -1:
            return vl
        return self._bisect_forward(x, start, 2*k + 2)
    
    # Returns min index s.t. start <= index and satisfy check(data[start:idx)) = True
    def bisect_forward(self, x, start=None):
        if start:
            ret = self._bisect_forward(x, start, 0)
        else:
            ret = self._bisect_forward(x, 0, 0)
        self._acc = self.e
        return ret

    def _bisect_backward(self, x, start, k):
        # When segment-k is at the bottom, accumulate and return.
        if k >= self.size - 1:
            self._acc = self.op(self._acc, self.data[k])
            if self._check(x, self._acc):
                return k - (self.size - 1)
            else:
                return -1
        width = 2**(self.lv - (k+1).bit_length() + 1)
        mid = (k+1) * width + width // 2 - self.size 
        # When right-child isn't in range, just look at right-child. 
        if mid >= start:
            return self._bisect_backward(x, start, 2*k + 1)
        # When segment-k is in range and has no answer in it, accumulate and return -1
        tmp_acc = self.op(self._acc, self.data[k])
        if start > mid + width // 2 and not self._check(x, tmp_acc):
            self._acc = tmp_acc
            return -1
        # Check right-child then left-child
        vl = self._bisect_backward(x, start, 2*k + 2)
        if vl != -1:
            return vl
        return self._bisect_backward(x, start, 2*k + 1)
    
    # Returns max index s.t. index < start and satisfy check(data[idx:start)) = True
    def bisect_backward(self, x, start=None):
        if start:
            ret = self._bisect_backward(x, start, 0)
        else:
            ret = self._bisect_backward(x, self.n, 0)
        self._acc = self.e
        return ret


n = int(input())
s = input().rstrip()
array = [0] * n
ST = SegmentTree(array)

event = []
for i, ch in enumerate(s):
    event.append((ch, i))
event.sort(reverse=True)

ans = [0] * n
for ch, index in event:
    val = ST.fold(0, index) + 1
    ans[index] = val
    ST.update(index, val)
print(max(ans))
print(*ans)

n = int(input())
s = list(input())

dg = 10**6
for i in range(n):
    s[i] = ord(s[i])*dg + i
s.sort()

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

ide_ele_max = 0

num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max


res = [0]*n
for e in s:
    ind = e%dg
    ad = query_max(ind,n)
    res[ind] = ad+1

    update_max(ind,ad+1)
print(max(res))
print(*res)

n=int(input())
s=list(map(ord,input()))
b=[0 for i in range(26)] #what the heck is an alphabet without 33 letters
ans=[]
for i in s:
    for j in range(26):
        if b[j]<=i:
            b[j]=i
            ans.append(j+1)
            break
print(26-b.count(0))
print(*ans)


import sys

# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

def ceil(tails, L, R, key): 
    while L + 1 < R: 
        m = (L + R) // 2
        if key < tails[m]:
            L = m 
        else: 
            R = m 
    return R
   
def LIS(a, n):
    
    tails = [0] * (n + 1)
    tails[0] = a[0]
    seq_len = 1  # LIS for a[:1]
    for i in range(1, n):
        
        if (a[i] > tails[0]):  # edit for other order
            tails[0] = a[i]    # new LIS start
            ans.append(1)
        
        elif (a[i] < tails[seq_len - 1]):  # edit for other order
            tails[seq_len] = a[i]          # extend existing LIS
            seq_len += 1
            ans.append(seq_len)
        
        else:  # find LIS that ends in a[i] and update tail value for it
            pos = ceil(tails, -1, seq_len - 1, a[i])
            tails[pos] = a[i]
            ans.append(pos + 1)
   
    return seq_len

n = int(input())
s = input()
ans = [1]
res = LIS(s, n)
print(res)
print(*ans)
    
# inf.close()


# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
# sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def check(m):
    if m == len(B):
        return True
    if B[m][-1][0] <= a:
        return True
    else:
        return False

N = INT()
A = [ord(c)-97 for c in input()]

B = [[] for i in range(1)]
B[0].append((A[0], 0))
for i, a in enumerate(A[1:], 1):
    idx = bisearch_min(-1, len(B), check)
    if idx == len(B):
        B.append([(a, i)])
    else:
        B[idx].append((a, i))

ans = [0] * N
for a, li in enumerate(B):
    for _, idx in li:
        ans[idx] = a + 1
print(len(B))
print(*ans)


n = int(input())
s = input()
kol = [-1] * n
cur = 1
ind = 0
while ind < n:
    if kol[ind] != -1:
        ind += 1
    else:
        kol[ind] = cur
        best = s[ind]
        for i in range(ind+1, n):
            if kol[i] != -1:
                continue
            else:
                if s[i] >= best:
                    kol[i] = cur
                    best = s[i]
        ind += 1
        cur += 1
print(max(kol))
for i in range(n):
    print(kol[i], end = " ")