#include #include #include #include #include #include #include #include #include #include using namespace std; template class BinaryIndexedTree_1_indexed{ void init(const vector &A){ for(int i=0; i tree; int N; BinaryIndexedTree_1_indexed(const int n) : tree(n+1,0), N(n){ } BinaryIndexedTree_1_indexed(const vector &A) : tree(A.size()+1,0), N(A.size()){ init(A); } //caution : position "i" must be 1-indexed void add(int i, const T x){ while(i <= N){ tree[i] += x; i += i & -i; } } //get sums [0,i] T get_sum(int i){ T ret=0; while(i>0){ ret += tree[i]; i -= i & -i; } return ret; } //get sums [from,to] T get_sums_range(const int from, const int to){ return get_sum(to) - get_sum(from-1); } //get at [i] T get_at(const int i){ return get_sum(i) - get_sum(i-1); } int lower_bound(T val){ if(val<=0) return 0; int x = 0; int k = 1; while((k<<1) <= N) k<<=1; for( ; k>0; k>>=1){ if( x+k <= N && tree[x+k] < val ){ val -= tree[x+k]; x += k; } } return x+1; } void print(){ for(int i=0; i<=N; i++){ cerr << tree[i] << " "; } cerr << endl; } }; int main(){ int N; cin >> N; string s; cin >> s; const string y = "yuki`"; vector alph(27, 0); for(int i=0; i BIT(alph); int ans = 0; int i = 0; while(N>0){ int a = BIT.get_at(y[i] - '`' +1); int b = BIT.get_sum(y[i] - '`' +1); if(a>0){ //s[i]と同じものが残っている BIT.add(y[i] - '`' +1, -1); N--; i++; }else if(N-b > 0){ //s[i]より大きいアルファベットが残ってる => 辞書順で大きいものが作れる //残ってるものの中で最小のアルファベットを探索 int pos = BIT.lower_bound(b+1); ans++; BIT.add(pos, -1); N--; i = 0; }else{ break; } } cout << ans << endl; return 0; }