#define MOD_TYPE 2 #include using namespace std; //#include #include //#include //#include using namespace atcoder; #if 0 #include #include using Int = boost::multiprecision::cpp_int; using lld = boost::multiprecision::cpp_dec_float_100; #endif #if 0 #include #include #include #include using namespace __gnu_pbds; using namespace __gnu_cxx; template using extset = tree, rb_tree_tag, tree_order_statistics_node_update>; #endif #if 1 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #pragma region Macros using ll = long long int; using ld = long double; using pii = pair; using pll = pair; using pld = pair; template using smaller_queue = priority_queue, greater>; #if MOD_TYPE == 1 constexpr ll MOD = ll(1e9 + 7); #else #if MOD_TYPE == 2 constexpr ll MOD = 998244353; #else constexpr ll MOD = 1000003; #endif #endif using mint = static_modint; constexpr int INF = (int)1e9 + 10; constexpr ll LINF = (ll)4e18; constexpr double PI = acos(-1.0); constexpr double EPS = 1e-11; constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0}; #define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i) #define rep(i, n) REP(i, 0, n) #define REPI(i, m, n) for (int i = m; i < (int)(n); ++i) #define repi(i, n) REPI(i, 0, n) #define YES(n) cout << ((n) ? "YES" : "NO") << "\n" #define Yes(n) cout << ((n) ? "Yes" : "No") << "\n" #define possible(n) cout << ((n) ? "possible" : "impossible") << "\n" #define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n" #define all(v) v.begin(), v.end() #define NP(v) next_permutation(all(v)) #define dbg(x) cerr << #x << ":" << x << "\n"; #define UNIQUE(v) v.erase(unique(all(v)), v.end()) struct io_init { io_init() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << setprecision(30) << setiosflags(ios::fixed); }; } io_init; template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } inline ll floor(ll a, ll b) { if (b < 0) a *= -1, b *= -1; if (a >= 0) return a / b; return -((-a + b - 1) / b); } inline ll ceil(ll a, ll b) { return floor(a + b - 1, b); } template inline void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } template vector compress(vector &v) { vector val = v; sort(all(val)), val.erase(unique(all(val)), val.end()); for (auto &&vi : v) vi = lower_bound(all(val), vi) - val.begin(); return val; } template constexpr istream &operator>>(istream &is, pair &p) noexcept { is >> p.first >> p.second; return is; } template constexpr ostream &operator<<(ostream &os, pair p) noexcept { os << p.first << " " << p.second; return os; } ostream &operator<<(ostream &os, mint m) { os << m.val(); return os; } ostream &operator<<(ostream &os, modint m) { os << m.val(); return os; } template constexpr istream &operator>>(istream &is, vector &v) noexcept { for (int i = 0; i < v.size(); i++) is >> v[i]; return is; } template constexpr ostream &operator<<(ostream &os, vector &v) noexcept { for (int i = 0; i < v.size(); i++) os << v[i] << (i + 1 == v.size() ? "" : " "); return os; } template constexpr void operator--(vector &v, int) noexcept { for (int i = 0; i < v.size(); i++) v[i]--; } random_device seed_gen; mt19937_64 engine(seed_gen()); struct BiCoef { vector fact_, inv_, finv_; BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); for (int i = 2; i < n; i++) { fact_[i] = fact_[i - 1] * i; inv_[i] = -inv_[MOD % i] * (MOD / i); finv_[i] = finv_[i - 1] * inv_[i]; } } mint C(ll n, ll k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n - k]; } mint P(ll n, ll k) const noexcept { return C(n, k) * fact_[k]; } mint H(ll n, ll k) const noexcept { return C(n + k - 1, k); } mint Ch1(ll n, ll k) const noexcept { if (n < 0 || k < 0) return 0; mint res = 0; for (int i = 0; i < n; i++) res += C(n, i) * mint(n - i).pow(k) * (i & 1 ? -1 : 1); return res; } mint fact(ll n) const noexcept { if (n < 0) return 0; return fact_[n]; } mint inv(ll n) const noexcept { if (n < 0) return 0; return inv_[n]; } mint finv(ll n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; BiCoef bc(200010); #pragma endregion // ------------------------------- #pragma region ImplicitTreap // T0: 元の配列のモノイド // T1: T0に対する作用素モノイド template class BaseImplicitTreap { // T0上の演算、単位元 virtual T0 f0(T0, T0) = 0; const T0 u0; // T1上の演算、単位元 virtual T1 f1(T1, T1) = 0; const T1 u1; // T0に対するT1の作用 virtual T0 g(T0, T1) = 0; // 多数のt1(T1)に対するf1の合成 virtual T1 p(T1, int) = 0; class xorshift { uint64_t x; public: xorshift() { mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); x = rnd(); for (int i = 0; i < 100; i++) { random(); } } uint64_t random() { x = x ^ (x << 7); return x = x ^ (x >> 9); } } rnd; struct Node { T0 value, acc; T1 lazy; int priority, cnt; bool rev; Node *l, *r; Node(T0 value_, int priority_, T0 u0_, T1 u1_) : value(value_), acc(u0_), lazy(u1_), priority(priority_), cnt(1), rev(false), l(nullptr), r(nullptr) {} } *root = nullptr; using Tree = Node *; int cnt(Tree t) { return t ? t->cnt : 0; } T0 acc(Tree t) { return t ? t->acc : u0; } void update_cnt(Tree t) { if (t) { t->cnt = 1 + cnt(t->l) + cnt(t->r); } } void update_acc(Tree t) { if (t) { t->acc = f0(acc(t->l), f0(t->value, acc(t->r))); } } void pushup(Tree t) { update_cnt(t), update_acc(t); } void pushdown(Tree t) { if (t && t->rev) { t->rev = false; swap(t->l, t->r); if (t->l) t->l->rev ^= 1; if (t->r) t->r->rev ^= 1; } if (t && t->lazy != u1) { if (t->l) { t->l->lazy = f1(t->l->lazy, t->lazy); t->l->acc = g(t->l->acc, p(t->lazy, cnt(t->l))); } if (t->r) { t->r->lazy = f1(t->r->lazy, t->lazy); t->r->acc = g(t->r->acc, p(t->lazy, cnt(t->r))); } t->value = g(t->value, p(t->lazy, 1)); t->lazy = u1; } pushup(t); } void split(Tree t, int key, Tree &l, Tree &r) { if (!t) { l = r = nullptr; return; } pushdown(t); int implicit_key = cnt(t->l) + 1; if (key < implicit_key) { split(t->l, key, l, t->l), r = t; } else { split(t->r, key - implicit_key, t->r, r), l = t; } pushup(t); } void insert(Tree &t, int key, Tree item) { Tree t1, t2; split(t, key, t1, t2); merge(t1, t1, item); merge(t, t1, t2); } void merge(Tree &t, Tree l, Tree r) { pushdown(l); pushdown(r); if (!l || !r) { t = l ? l : r; } else if (l->priority > r->priority) { merge(l->r, l->r, r), t = l; } else { merge(r->l, l, r->l), t = r; } pushup(t); } void erase(Tree &t, int key) { Tree t1, t2, t3; split(t, key + 1, t1, t2); split(t1, key, t1, t3); merge(t, t1, t2); } void update(Tree t, int l, int r, T1 x) { if (l >= r) return; Tree t1, t2, t3; split(t, l, t1, t2); split(t2, r - l, t2, t3); t2->lazy = f1(t2->lazy, x); t2->acc = g(t2->acc, p(x, cnt(t2))); merge(t2, t2, t3); merge(t, t1, t2); } T0 query(Tree t, int l, int r) { if (l == r) return u0; Tree t1, t2, t3; split(t, l, t1, t2); split(t2, r - l, t2, t3); T0 ret = t2->acc; merge(t2, t2, t3); merge(t, t1, t2); return ret; } // [l, r)の中で左から何番目か int find(Tree t, T0 x, int offset, bool left = true) { if (f0(t->acc, x) == x) { return -1; } else { if (left) { if (t->l && f0(t->l->acc, x) != x) { return find(t->l, x, offset, left); } else { return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left); } } else { if (t->r && f0(t->r->acc, x) != x) { return find(t->r, x, offset + cnt(t->l) + 1, left); } else { return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left); } } } } void reverse(Tree t, int l, int r) { if (l > r) return; Tree t1, t2, t3; split(t, l, t1, t2); split(t2, r - l, t2, t3); t2->rev ^= 1; merge(t2, t2, t3); merge(t, t1, t2); } // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様 void rotate(Tree t, int l, int m, int r) { reverse(t, l, r); reverse(t, l, l + r - m); reverse(t, l + r - m, r); } void dump(Tree t) { if (!t) return; pushdown(t); dump(t->l); cout << t->value << " "; dump(t->r); } public: BaseImplicitTreap(T0 u0_, T1 u1_) : u0(u0_), u1(u1_) {} void set_by_vector(const vector &a) { for (int i = 0; i < a.size(); i++) { insert(i, a[i]); } } int size() { return cnt(root); } void insert(int pos, T0 x) { insert(root, pos, new Node(x, rnd.random(), u0, u1)); } void update(int l, int r, T1 x) { update(root, l, r, x); } T0 query(int l, int r) { return query(root, l, r); } // 二分探索。[l, r)内のkでf0(tr[k], x) != // xとなる最左/最右のもの。存在しない場合は-1 // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す int binary_search(int l, int r, T0 x, bool left = true) { if (l >= r) return -1; Tree t1, t2, t3; split(root, l, t1, t2); split(t2, r - l, t2, t3); int ret = find(t2, x, l, left); merge(t2, t2, t3); merge(root, t1, t2); return ret; } void erase(int pos) { erase(root, pos); } void reverse(int l, int r) { reverse(root, l, r); } void rotate(int l, int m, int r) { rotate(root, l, m, r); } void dump() { dump(root); cout << "\n"; } T0 operator[](int pos) { return query(pos, pos + 1); } }; template struct MinUpdateQuery : public BaseImplicitTreap { using BaseImplicitTreap::BaseImplicitTreap; MinUpdateQuery() : MinUpdateQuery(numeric_limits::max(), numeric_limits::min()) {} T0 f0(T0 x, T0 y) override { return min(x, y); } T1 f1(T1 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T0 g(T0 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T1 p(T1 x, int len) override { return x; } }; template struct SumAddQuery : public BaseImplicitTreap { using BaseImplicitTreap::BaseImplicitTreap; SumAddQuery() : SumAddQuery(0, 0) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return x + y; } T0 g(T0 x, T1 y) override { return x + y; } T1 p(T1 x, int len) override { return x * len; } }; template struct MinAddQuery : public BaseImplicitTreap { using BaseImplicitTreap::BaseImplicitTreap; MinAddQuery() : MinAddQuery(numeric_limits::max(), 0) {} T0 f0(T0 x, T0 y) override { return min(x, y); } T1 f1(T1 x, T1 y) override { return x + y; } T0 g(T0 x, T1 y) override { return x + y; } T1 p(T1 x, int len) override { return x; } }; template struct SumUpdateQuery : public BaseImplicitTreap { using BaseImplicitTreap::BaseImplicitTreap; SumUpdateQuery() : SumUpdateQuery(0, numeric_limits::min()) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T0 g(T0 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T1 p(T1 x, int len) override { return x == numeric_limits::min() ? numeric_limits::min() : x * len; } }; template struct SumAffineQuery : public BaseImplicitTreap> { using T1 = pair; // first * x + second using BaseImplicitTreap::BaseImplicitTreap; SumAffineQuery() : SumAffineQuery(0, {1, 0}) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; } T0 g(T0 x, T1 y) override { return y.first * x + y.second; } T1 p(T1 x, int len) override { return {x.first, x.second * len}; } // update(i, j, {a, b}); // [i, j)にax + bを作用 // update(i, j, {0, a}); // update // update(i, j, {1, a}); // 加算 // update(i, j, {a, 0}); // 倍 }; template struct MinmaxAffineQuery : public BaseImplicitTreap, pair> { using T0 = pair; // {min, max} using T1 = pair; // first * x + second using BaseImplicitTreap::BaseImplicitTreap; MinmaxAffineQuery() : MinmaxAffineQuery({numeric_limits::max(), -numeric_limits::max()}, {1, 0}) { } // TODO: _u1を使うとコンパイル通らない原因不明 T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; } T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; } T0 g(T0 x, T1 y) override { T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second}; if (y.first < 0) swap(ret.first, ret.second); return ret; } T1 p(T1 x, int len) override { return x; } // update(i, j, {a, b}); // [i, j)にax + bを作用 // update(i, j, {0, a}); // update // update(i, j, {1, a}); // 加算 // update(i, j, {a, 0}); // 倍 }; // https://xuzijian629.hatenablog.com/entry/2019/10/25/234938 #pragma endregion void solve() { int n; string s; cin >> n >> s; const string AGCT = "AGCT"; vector AGCT_int; for (auto c : AGCT) AGCT_int.push_back(c - 'A'); int cnt[26] = {}; for (auto c : s) cnt[c - 'A']++; modint::set_mod(26); vector si(n); rep(i, n) si[i] = s[i] - 'A'; SumAddQuery treap; treap.set_by_vector(si); int ans = 0; int len = n; while (1) { int sum = 0; for (auto i : AGCT_int) { sum += cnt[i]; } if (sum == 0) break; ans++; int del = treap[sum - 1].val(); cnt[del]--; treap.erase(sum - 1); len--; treap.update(0, len, cnt[del]); rotate(cnt, cnt + 26 - cnt[del] % 26, cnt + 26); } cout << ans << "\n"; } int main() { solve(); }