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 ≤ n ≤ 2 ⋅ 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 ≤ res ≤ 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 ≤ c_i ≤ 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 
   //  package com.company;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.lang.reflect.Array;
    import java.sql.SQLOutput;
    import java.util.*;
    public class Main {

        public static void main(String[] args) throws IOException {
            Scanner s = new Scanner(System.in);
            //BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb1 = new StringBuilder();//int n=Integer.parseInt(s.readLine());
             int n=s.nextInt();
             char[] a=new char[n];
             a=s.next().toCharArray();
             int[] c=new int[n];int flag=0;int max=0;
             int[] val=new int[123];int ans=1;
             for(int i=0;i<n;i++){max=0;
                for(int j=a[i]+1;j<123;j++){
                    max=Math.max(val[j],max);
                }
                val[a[i]]=max+1;
                ans=Math.max(ans,val[a[i]]);
                sb1.append(val[a[i]]+" ");

             }
            System.out.println(ans);
            System.out.println(sb1.toString());

        }
        static void dfs(int i,ArrayList<Integer>[] adj,int[] vis,int n){
            vis[i]=1;
            if(adj[i]==null){return;}
            for(Integer j:adj[i]){
                if(vis[j]==0){
                     dfs(j,adj,vis,n);
                }
            }}
        static  void computeLPSArray(String pat, int M, int lps[])
        {
            int len = 0;
            int i = 1;
            lps[0] = 0;
            while (i < M) {
                if (pat.charAt(i) == pat.charAt(len)) {
                    len++;
                    lps[i] = len;
                    i++;
                }
                else // (pat[i] != pat[len])
                {
                    if (len != 0) {
                        len = lps[len - 1];
                    }
                    else // if (len == 0)
                    {
                        lps[i] = len;
                        i++;
                    }
                }
            }
        }
        static boolean isPrime(int n)
        {
            if (n <= 1) return false;
            if (n <= 3) return true;

            if (n % 2 == 0 || n % 3 == 0) return false;

            for (int i = 5; i * i <= n; i = i + 6)
                if (n % i == 0 || n % (i + 2) == 0)
                    return false;

            return true;
        }

        static double power(double x, long y, int p) {
            double res = 1;
            x = x % p;
            while (y > 0) {
                if ((y & 1) == 1)
                    res = (res * x) % p;
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }
        public static void fracion(double x) {
            String a = "" + x;
            String spilts[] = a.split("\\."); // split using decimal
            int b = spilts[1].length(); // find the decimal length
            int denominator = (int) Math.pow(10, b); // calculate the denominator
            int numerator = (int) (x * denominator); // calculate the nerumrator Ex
            // 1.2*10 = 12
            int gcd = (int)gcd((long)numerator, denominator); // Find the greatest common
            // divisor bw them
            String fraction = "" + numerator / gcd + "/" + denominator / gcd;
            // System.out.println((denominator/gcd));
            long x1=modInverse(denominator / gcd,998244353  );
            //  System.out.println(x1);
            System.out.println((((numerator / gcd )%998244353 *(x1%998244353  ))%998244353  ) );
        }static int anst=Integer.MAX_VALUE;
      static StringBuilder sb1=new StringBuilder();
        public static int bfs(int i1, ArrayList<Integer>[] h, int[] vis, int n,int val1) {
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(i1);Queue<Integer> aq=new LinkedList<Integer>();
            aq.add(0);
            while(!q.isEmpty()){
                int i=q.poll();
                int val=aq.poll();
                if(i==n){
                    return val;
                }
                if(h[i]!=null){
                    for(Integer j:h[i]){
                       if(vis[j]==0){
                        q.add(j);vis[j]=1;
                           aq.add(val+1);}
                    }
                }
            }return -1;
        }
        static int i(String a) {
            return Integer.parseInt(a);
        }
        static long l(String a) {
            return Long.parseLong(a);
        }
        static String[] inp() throws IOException {
            BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
            return s.readLine().trim().split("\\s+");
        }


        static long gcd(long a, long b) {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }
        static long modInverse(int a, int m)
        {


            {
                // If a and m are relatively prime, then modulo inverse
                // is a^(m-2) mode m
                return (power(a, m - 2, m));
            }
        }

        // To compute x^y under modulo m
        static long power(int x, int y, int m)
        {
            if (y == 0)
                return 1;

            long p = power(x, y / 2, m) % m;
            p = (p * p) % m;

            if (y % 2 == 0)
                return p;
            else
                return (x * p) % m;
        }

        // Function to return gcd of a and b

    }
    class Student
    {
        int l;int r;
        public Student(int l, int r) {
            this.l = l;
            this.r = r;
        }
        // Constructor


        // Used to print student details in main()
        public String toString()
        {
            return this.l+" ";
        }
    }

    class Sortbyroll implements Comparator<Student>
    {
        // Used for sorting in ascending order of
        // roll number
        public int compare(Student a, Student b){
            return a.l-b.l;  }
    } class Sortbyroll1 implements Comparator<Student>
    {
        // Used for sorting in ascending order of
        // roll number
        public int compare(Student a, Student b){
            return a.l-b.l;
        }
    }