#include using namespace std; using ll = long long; using ld = long double; using pii = pair; using pli = pair; using pll = pair; using Graph = vector>; const string Yes="Yes"; const string No="No"; const string YES="YES"; const string NO="NO"; const string abc="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const ll MOD=1000000007; const ll mod=998244353; const long long INF = 1LL << 60; const long double PI=3.141592653589793; #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second #define YESNO(T) if(T){cout<<"YES"<>vec[i]; #define outV(vec) for(ll i=0;i inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } //DFS map>Gra; mapvisited;// false=not visited, true=visited ll hen=0; void DFS(int pos){ visited[pos]=true; for(int i : Gra[pos]){ if(visited[i]==false)DFS(i); } } //BFS const vectordx = {0, 1, 0, -1}; const vectordy = {1, 0, -1, 0}; vector> BFS(int H, int W, const vector &G, pair s) { vector> dist(H, vector(W, -1)); //すべての頂点を未訪問に初期化 queue> que; //初期条件 (頂点sを初期頂点とする) dist[s.first][s.second] = 0; que.push(s); // sを探索済み頂点に // BFS開始 while (!que.empty()) { pair v = que.front(); que.pop(); //頂点vからたどれる頂点を全て調べる for (int i = 0; i < 4; i++) { int X = dx[i] + v.first; int Y = dy[i] + v.second; if (X < 0 || X >= H || Y < 0 || Y >= W) continue; //すでに発見済みの頂点は探索しない if (dist[X][Y] != -1 || G[X][Y] == '#') continue; //新たな未探索点xについて距離情報を更新してキューに挿入 dist[X][Y] = dist[v.first][v.second] + 1; que.push(make_pair(X, Y)); } } return dist; } //エラトステネスの篩 vectorPrime(2,false);//false=not Prime number, true=Prime Number void Era(ll N){ for(ll i=0;i 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } //素因数分解 vector > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } //割り算 ll Div(ll a,ll b,ll m){ return (a * modpow(b,m-2,m)) % m; } //階乗 vectorfact(1); void fac(ll N,ll m){ fact[0]=1; for(int i=1;i<=N;i++){ fact.pb(fact[i-1]*(i)); fact[i]%=m; } } //組み合わせ ll comb(ll n,ll r,ll m){ return Div(fact[n],fact[r] * fact[n-r] % m,m); } //UnionFind struct UnionFind { vector par, rank, siz; // 構造体の初期化 UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { } // 根を求める int root(int x) { if (par[x]==-1) return x; // x が根の場合は x を返す else return par[x] = root(par[x]); // 経路圧縮 } // x と y が同じグループに属するか (= 根が一致するか) bool same(int x, int y) { return root(x)==root(y); } // x を含むグループと y を含むグループを併合する bool unite(int x, int y) { int rx = root(x), ry = root(y); // x 側と y 側の根を取得する if (rx==ry) return false; // すでに同じグループのときは何もしない // union by rank if (rank[rx]> &G, int s, vector &dis) { int N = G.size(); dis.resize(N, INF); priority_queue, vector>, greater>> pq; // 「仮の最短距離, 頂点」が小さい順に並ぶ dis[s] = 0; pq.emplace(dis[s], s); while (!pq.empty()) { pair p = pq.top(); pq.pop(); int v = p.second; if (dis[v] < p.first) { // 最短距離で無ければ無視 continue; } for (auto &e : G[v]) { if (dis[e.to] > dis[v] + e.cost) { // 最短距離候補なら priority_queue に追加 dis[e.to] = dis[v] + e.cost; pq.emplace(dis[e.to], e.to); } } } } //https://algo-logic.info/dijkstra/ //ワーシャルフロイド void warshall_floyd(vector> &dist) { for (int k = 0; k < (int)dist.size(); k++) { for (int i = 0; i < (int)dist.size(); i++) { for (int j = 0; j < (int)dist.size(); j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } //https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75 //計算幾何学 //ベクトル B-A pair bector(pair A,pair B){ return mp(B.first - A.first , B.second - A.second); } //内積(a,bはベクトル)、内積は90度が0で角度が小さいほど大きい ll inner(pair a,pair b){ return a.first*b.first+a.second+b.second; } //外積(a,bはベクトル)、反時計だと負、時計だと正 ll outer(pair a,pair b){ return a.first*b.second-a.second*b.first; } long long merge_cnt(vector &a) { long long n = a.size(); if (n <= 1) return 0; long long cnt = 0; vector b(a.begin(), a.begin()+n/2); vector c(a.begin()+(n/2), a.end()); cnt += merge_cnt(b); cnt += merge_cnt(c); long long ai = 0, bi = 0, ci = 0; while (ai < n) { if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) { a[ai++] = b[bi++]; } else { cnt += n / 2 - bi; a[ai++] = c[ci++]; } } return cnt; } /*UnionFindはUnionFind uf(頂点の数)と書こう uniteは合併 sameが判定 sizeがサイズ セグ木をやれ!! I am a cyan coder. 精進しろ!! */ ll manhattan(pll A,pll B){ return(abs(A.fi-B.fi)+abs(A.se-B.se)); } int main(){ ll N; string s; cin>>N>>s; vector>dp(N); for(int i=1;i