#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; const double PI = 3.14159265358979323846; const double EPS = 1e-12; const ll INF = 1LL<<29; const ll mod = 1e9+7; #define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i)) #define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d)) #define all(v) (v).begin(), (v).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset((m),(v),sizeof(m)) #define chmin(X,Y) ((X)>(Y)?X=(Y),true:false) #define chmax(X,Y) ((X)<(Y)?X=(Y),true:false) #define fst first #define snd second #define UNIQUE(x) (x).erase(unique(all(x)),(x).end()) template ostream &operator<<(ostream &os, const vector &v){int n=v.size();rep(i,n)os< v(n); rep(i, n) v[i] = s[i]=='#'?1:-1; int left = n-1, right = 0; int cnt = 0; rep(i, n) if(v[i]==1){ left = min(left, i); right = max(right, i); cnt++; } int res = 0; auto inc = [&]{ x++; res++; v[x] *= -1; cnt += v[x]; }; auto dec = [&]{ x--; res++; v[x] *= -1; cnt += v[x]; }; while(x>0 && x>left){ dec(); //x--; res++; v[x] *= -1; cnt += v[x]; } if(v[x]==1){ if(cnt==1) return 3; //int d = b?-1:1; if(x+1<0 || n<=x+1) return INF; inc(); //x++; res++; v[x] *= -1; cnt += v[x]; dec(); } while(cnt){ if(x>0 && v[x-1]==1) dec(); else if(x>n>>s; n--; ll res = min(solve(s, n, 0), solve(s, n, 1)); reverse(all(s)); n = s.size()-n-1; res = min(res, min(solve(s, n, 0), solve(s, n, 1))); cout<