For a string \(T\) of length \(L\) consisting of d and p, let \(f(T)\) be \(T\) rotated \(180\) degrees. More formally, let \(f(T)\) be the string that satisfies the following conditions.

\(f(T)\) is a string of length \(L\) consisting of d and p.

For every integer \(i\) such that \(1 \leq i \leq L\), the \(i\)-th character of \(f(T)\) differs from the \((L + 1 - i)\)-th character of \(T\).

For instance, if \(T =\) ddddd, \(f(T) =\) ppppp; if \(T =\) dpdppp, \(f(T)=\) dddpdp.

You are given a string \(S\) of length \(N\) consisting of d and p.

You may perform the following operation zero or one time.

Choose a pair of integers \((L, R)\) such that \(1 \leq L \leq R \leq N\), and let \(T\) be the substring formed by the \(L\)-th through \(R\)-th characters of \(S\). Then, replace the \(L\)-th through \(R\)-th characters of \(S\) with \(f(T)\).

For instance, if \(S=\) dpdpp and \((L,R)=(2,4)\), we have \(T=\) pdp and \(f(T)=\) dpd, so \(S\) becomes ddpdp.

Print the lexicographically smallest string that \(S\) can become.

1≤N≤5000

给出一个长度为 \(N(1 \le N \le 5000)\) 的字符串 \(S\)，且 \(\forall S_i,S_i \in \{d,p\}\)。

定义 \(\operatorname{rotate}(l,r)\)，对于区间 \([l,r]\) 的每一个 \(i\)，重新赋值 \(S_i\)，使得 \(S_i \neq S_{r+l-i}\)。（即，对称的）

你需要执行0或1次 \(\operatorname{rotate}(l,r)\)（\(l,r\) 是任意的），使得 \(S\) 字典序最小。

考虑贪心，遇到的第一个 \(p\) 为 \(l\)，然后暴力枚举 \(r\) 找答案即可。

时间复杂度 \(O(N^{2})\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
string s,bk,ret;
int l;
int r[1000005],tot;

signed main(){
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='d'){
            continue;
        }
        else{
            l=i;
            break;
        }
    }
    bk=s;
    ret=s;
    for(int i=l;i<n;i++){
        s=bk;
        int L=l,R=i;
        for(int j=L,k=R;j<=R;j++,k--){
            if(bk[k]=='d'){
                s[j]='p';
            }
            else{
                s[j]='d';
            }
        }
        if(s<ret){
            ret=s;
        }
    }
    cout<<ret<<'\n';
    return 0;
}