using System.Text;using System.Numerics;using System.Runtime.CompilerServices;using System;using System.Collections.Generic;using System.Linq;using System.IO;using System.Security.Cryptography;using System.Buffers;using System.Diagnostics; #nullable enable var fs = new FastScanner(); var sb = new StringBuilder(); int N=fs.Int(); var S=fs.String(); var nxt=Nms.Array(N, -1); var st=new Stack(); for(int i=0; i0) nxt[st.Peek()]=i; st.Push(i); } var arriveAt=Nms.Array(N, 0); while(st.Count>0) { var u=st.Pop(); arriveAt[u]=Math.Max(N-u, nxt[u]<0 ? 0 : arriveAt[nxt[u]]+2); if(st.Count==0) sb.Append(arriveAt[u]).AppendLine(); } Console.Write(sb.ToString()); Console.Out.Flush(); Environment.Exit(0); static class Nms { public static T[] Array(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; i++) a[i] = f(); return a; } public static T[] Array(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; i++) a[i] = f(i); return a; } public static T[] Array(int n, T val) { var a = new T[n]; for (int i = 0; i < n; i++) a[i] = val; return a; } public static T[][] Matrix(int h, int w, Func f) { var a = new T[h][]; for (int i = 0; i < h; ++i) { a[i] = new T[w]; for (int j = 0; j < w; ++j) a[i][j] = f(); } return a; } public static T[][] Matrix(int h, int w, Func f) { var a = new T[h][]; for (int i = 0; i < h; ++i) { a[i] = new T[w]; for (int j = 0; j < w; ++j) a[i][j] = f(i, j); } return a; } public static T[][] Matrix(int h, int w, T val) { var a = new T[h][]; for (int i = 0; i < h; ++i) { a[i] = new T[w]; for (int j = 0; j < w; ++j) a[i][j] = val; } return a; } public static StackArray Stack() => new StackArray();} sealed class Count { private readonly int n; private readonly long mod; private readonly long[] fact; private readonly long[] inv; public Count(int n, long mod) { ++n; this.n = n; this.mod = mod; fact = new long[n]; fact[0] = fact[1] = 1 % mod; for (int i = 2; i < n; ++i) fact[i] = fact[i - 1] * i % mod; inv = new long[n]; inv[n - 1] = Sugaku.ModPow(fact[n - 1], mod - 2, mod); for (int i = n - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod; } public long P(int a, int b) => (a < 0 || b < 0 || b > a) ? 0 : fact[a] * inv[a - b] % mod; public long C(int a, int b) => (a < 0 || b < 0 || b > a) ? 0 : fact[a] * inv[a - b] % mod * inv[b] % mod; public long H(int a, int b) => C(a + b - 1, a - 1); /// /// choose k from n /// /// /// /// public long Binom(int n, int k) => C(n, k); /// /// choose k from n and sort /// /// /// /// public long Arrange(int n, int k) => P(n, k); /// /// have k share n /// /// /// /// public long Share(int n, int k) => C(n + k - 1, n); /// /// split n into nonempty k /// /// /// /// public long Part(int n, int k) => C(n - 1, k - 1); /// /// split n members into nonempty k teams /// /// /// /// public long TeamUp(int n, int k) { if (n < 0 || k < 0 || n < k) return 0; long sum = 0; for (int i = 0; i <= k; ++i) { long t = (k - i) % 2 == 0 ? 1 : -1; t *= C(k, i) * Sugaku.ModPow(i, n, mod) % mod; sum = (sum + mod + t) % mod; } return sum; } /// /// split n members into nonempty k groups /// /// /// /// public long GroupUp(int n, int k) => TeamUp(n, k) * inv[k] % mod; /// /// classify n members using k unlabeled groups /// /// /// /// public long Classify(int n, int k) { if (n < 0 || k < 0) return 0; var p = Nms.Array(k + 1, 0); for (int i = 0; i <= k; ++i) { p[i] = i % 2 == 1 ? (mod - inv[i]) % mod : inv[i]; if (i > 0) p[i] = (p[i] + p[i - 1]) % mod; } long sum = 0; for (int i = 0; i <= k; ++i) { sum = (sum + inv[i] * Sugaku.ModPow(i, n, mod) % mod * p[k - i]) % mod; } return sum; } /// /// represent n using k unordered elements /// /// /// public long Represent(int n, int k) { var dp = Nms.Matrix(n + 1, k + 1, 0); for (int j = 0; j <= k; ++j) { dp[0][j] = 1; } for (int i = 1; i <= n; ++i) for (int j = 1; j <= k; ++j) { dp[i][j] = (dp[i][j - 1] + (i - j >= 0 ? dp[i - j][j] : 0)) % mod; } return dp[n][k]; } } class StackArray(int n = 128) { private T[] v = new T[n]; private int count = 0; private int n = n; public void Push(T val) { if (count == n) { var x = new T[2 * n]; Array.Copy(v, x, count); v = x; n <<= 1; } v[count++] = val; } public T Peek() { Validate(0); return v[count - 1]; } public T Pop() { Validate(0); T item = v[--count]; v[count] = default!; return item; } public int Count => count; public T this[int k] { get { Validate(k); return v[k]; } } private void Validate(int t) { if (t < 0 || t >= count) throw new IndexOutOfRangeException(); } } static class Sugaku { public static long ModPow(long b, long r, long MOD) { long res = 1; b %= MOD; while (r > 0) { if ((r & 1) != 0) res = res * b % MOD; b = b * b % MOD; r >>= 1; } return res; }} class FastScanner { private readonly Stream stream = Console.OpenStandardInput(); private readonly byte[] buffer = new byte[1 << 16]; private int ptr = 0, len = 0; private byte Read() { if (ptr >= len) { len = stream.Read(buffer, 0, buffer.Length); ptr = 0; if (len == 0) return 0; } return buffer[ptr++]; } public int Int() { int c; while ((c = Read()) <= ' ') if (c == 0) return 0; int sign = 1; if (c == '-') { sign = -1; c = Read(); } int val = c - '0'; while ((c = Read()) >= '0') { checked { val = val * 10 + c - '0'; } } return val * sign; } public (int, int) Int2() => (Int(), Int()); public (int, int, int) Int3() => (Int(), Int(), Int()); public (int, int, int, int) Int4() => (Int(), Int(), Int(), Int()); public long Long() { int c; while ((c = Read()) <= ' ') if (c == 0) return 0; int sign = 1; if (c == '-') { sign = -1; c = Read(); } long val = c - '0'; while ((c = Read()) >= '0') val = val * 10 + c - '0'; return val * sign; } public (long, long) Long2() => (Long(), Long()); public (long, long, long) Long3() => (Long(), Long(), Long()); public (long, long, long, long) Long4() => (Long(), Long(), Long(), Long()); public (int, long) IntLong() => (Int(), Long()); public int[] Digits() { var s = this.String(); var res = new int[s.Length]; for (int i = 0; i < s.Length; ++i) res[i] = s[i] - '0'; return res; } public string String() { int c; while ((c = Read()) <= ' ') if (c == 0) return ""; var sb = new StringBuilder(); do { sb.Append((char)c); c = Read(); } while (c > ' '); return sb.ToString(); } public (string, string) String2() => (String(), String()); public (string, string, string) String3() => (String(), String(), String()); public double Double() { int c; while ((c = Read()) <= ' ') if (c == 0) return 0; int sign = 1; if (c == '-') { sign = -1; c = Read(); } double val = 0; // integer part while (c >= '0' && c <= '9') { val = val * 10 + (c - '0'); c = Read(); } // fractional part if (c == '.') { double scale = 1; while ((c = Read()) >= '0' && c <= '9') { scale *= 0.1; val += (c - '0') * scale; } } // exponent part if (c == 'e' || c == 'E') { int esign = 1; int exp = 0; c = Read(); if (c == '-') { esign = -1; c = Read(); } else if (c == '+') { c = Read(); } while (c >= '0' && c <= '9') { exp = exp * 10 + (c - '0'); c = Read(); } val *= Math.Pow(10, esign * exp); } return val * sign; } public (double, double) Double2() => (Double(), Double()); public (double, double, double) Double3() => (Double(), Double(), Double()); public char Char() { int c; while ((c = Read()) <= ' ') if (c == 0) return '\0'; return (char)c; } }