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 junit_testing;

import java.util.*;
import java.lang.*;
import java.io.*;

public class E1 {
	private static FastReader fr;
	private static OutputStream out;
	private static int mod = (int)(1e9+7);
	
	private void solve() {
		int n = fr.nextInt();
		char ch[] = fr.next().toCharArray();
		int col[] = new int[n];
		Arrays.fill(col, -1);
		
		for(char c='z';c>='a';c--) {
			HashSet<Integer> set = new HashSet<>();
			for(int i=0;i<n;i++) {
				if(ch[i] == c) {
					col[i] = set.size() + 1;
				}else if(ch[i] > c && !set.contains(col[i])) {
					set.add(col[i]);
				}
			}
			set.clear();
		}
		
		HashSet<Integer> set = new HashSet<>();
		for(int i=0;i<n;i++) {
			if(!set.contains(col[i])) {
				set.add(col[i]);
			}
		}
		println(set.size());
		printArray(col);
	}
	
	public void printArray(int arr[]) {
		for(int val: arr) {
			print(val + " ");
		}
		println("");
	}
	
	public static void main(String args[]) throws IOException{
		new E1().run();
	}
	
	private ArrayList<Integer> factors(int n, boolean include){
		ArrayList<Integer> factors = new ArrayList<>();
		if(n < 0)
			return factors;
		
		if(include) {
			factors.add(1);
			if(n > 1)
				factors.add(n);
		}
		
		int i = 2;
		for(;i*i<n;i++) {
			if(n % i == 0) {
				factors.add(i);
				factors.add(n / i);
			}
		}
		
		if(i * i == n) {
			factors.add(i);
		}
		
		return factors;
	}
	
	private ArrayList<Integer> PrimeFactors(int n) {
	    ArrayList<Integer> primes = new ArrayList<>();
	 
	    int i = 2;
	    while (i * i <= n) {
	      if (n % i == 0) {
	        primes.add(i);
	 
	        while (n % i == 0) {
	          n /= i;
	        }
	      }
	 
	      i++;
	    }
	 
	    if (n > 1) {
	      primes.add(n);
	    }
	 
	    return primes;
	  }
	
	private boolean isPrime(int n) {
		if(n == 0 || n == 1) {
			return false;
		}
		
		if(n % 2 == 0) {
			return false;
		}
		
		for(int i=3;i*i<=n;i+=2) {
			if(n % i == 0) {
				return false;
			}
		}
		
		return true;
	}

	private ArrayList<Integer> Sieve(int n){
		boolean bool[] = new boolean[n+1];
		Arrays.fill(bool, true);
		bool[0] = bool[1] = false;
		
		for(int i=2;i*i<=n;i++) {
			if(bool[i]) {
				int j = 2;
				while(i*j <= n) {
					bool[i*j] = false;
					j++;
				}
			}
		}
		
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i=2;i<=n;i++) {
			if(bool[i])
				primes.add(i);
		}
		
		return primes;
	}
	
	private HashMap<Integer, Integer> addToHashMap(HashMap<Integer, Integer> map, int arr[]){
		for(int val: arr) {
			if(!map.containsKey(val)) {
				map.put(val, 1);
			}else {
				map.put(val, map.get(val) + 1);
			}
		}
		return map;
	}
	
	private int factorial(int n) {
		long fac = 1;
		for(int i=2;i<=n;i++) {
			fac *= i;
			fac %= mod;
		}
		return (int)(fac % mod);
	}

	private static int pow(int base,int exp){
		if(exp == 0){
			return 1;
		}else if(exp == 1){
			return base;
		}
		int a = pow(base,exp/2);
		a = ((a % mod) * (a % mod)) % mod;
		if(exp % 2 == 1) {
			a = ((a % mod) * (base % mod));
		}
		return a;
	}

	private static int gcd(int a,int b){
		if(a == 0){
			return b;
		}
		
		return gcd(b%a,a);
	}
	
	private static int lcm(int a,int b){
		return (a * b)/gcd(a,b);
	}
	
	private void run() throws IOException{
		fr = new FastReader();
		out = new BufferedOutputStream(System.out);
		solve();
		out.flush();
		out.close();
	}
	
	private static class FastReader{
		private static BufferedReader br; 
		private static StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedOutputStream(System.out);
		}
		
		public String next() {
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken();
		}
		
		public String nextLine() { 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		 
		public char[] nextCharArray() {
			return next().toCharArray();
		}
		
		public int[] nextIntArray(int n) {
			int arr[] = new int[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
		
		public long[] nextLongArray(int n) {
			long arr[] = new long[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public String[] nextStringArray(int n) {
			String arr[] = new String[n];
			for(int i=0;i<n;i++) {
				arr[i] = next();
			}
			return arr;
		}
		
	}

	public static void print(Object str) {
        try {
            out.write(str.toString().getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println(Object str) {
        try {
            out.write((str.toString() + "\n").getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println() {
		println("");
	}
	
	public static void printArray(Object str[]){
		for(Object s : str) {
			try {
	            out.write(str.toString().getBytes());
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
		}
	}
}
