---
tags: CP
---

# ncku judge 93 (FFT, 卷積)

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define add insert
#define Int long long
#define pdd pair<double,double>
#define pii pair<int,int>
#define pII pair<Int,Int>
#define sqr(x) ((x)*(x))
#define PI acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define x first
#define y second
using namespace std;

typedef complex<double> CD;

void FFT(vector<CD> &a, bool inv) {
	//bit reversal
	int n = a.size();
	for(int i=0, j=0; i < n; i++) {
		if(j > i) swap(a[i], a[j]);
		int k = n;
		while(j & (k >>=1)) j &=~k;
		j |= k;
	}
	double pi = inv? -PI:PI;
	for(int step=1; step < n; step <<= 1) {
		double alpha = pi/step;
		for(int k = 0; k < step; k++) {
			CD omegak = exp(CD(0, alpha*k));
			for(int Ek = k; Ek < n; Ek += step << 1) {
				int Ok = Ek + step;
				CD t = omegak * a[Ok];
				a[Ok] = a[Ek] - t;
				a[Ek] += t;
			}
		}
	}
	if(inv) for(int i = 0; i < n; i++) a[i] /= n;
}

inline vector<double> operator * (const vector<double>& v1, const vector<double>& v2) {
	int s1 = v1.size(), s2 = v2.size(), S = 2;
	while(S < s1+s2) S <<= 1;
	vector<CD> a(S,0), b(S,0);
	for(int i = 0; i < s1; i++) a[i] = v1[i];
	for(int i = 0; i < s2; i++) b[i] = v2[i];
	FFT(a, false);
	FFT(b, false);
	for(int i = 0; i < S; i++) a[i] *= b[i];
	FFT(a, true);
	vector<double> res(s1+s2-1);
	for(int i = 0; i < s1+s2-1; i++) res[i] = a[i].real();
	return res;
}

bool match(char a, char b) {
	if(a > b) swap(a, b);
	if(a == 'A' && b == 'T') return 1;
	else if(a == 'C' && b == 'G') return 1;
	return 0;
}

void solve(){
	int n; cin >> n;
	string str; cin >> str;
	vector<double> A(n,0), B(n,0), res1, res2;
	vector<int> res;
	for(int i = 0; i < n; i++) if(str[i] == 'A') A[i] = 1.0;
	for(int i = 0; i < n; i++) if(str[i] == 'T') B[i] = 1.0;
	res1 = A*B;
	A.clear();
	B.clear();
	A.assign(n, 0);
	B.assign(n, 0);
	for(int i = 0; i < n; i++) if(str[i] == 'C') A[i] = 1.0;
	for(int i = 0; i < n; i++) if(str[i] == 'G') B[i] = 1.0;
	res2 = A*B;
	res.resize(res1.size());
	int nn = res.size();
	for(int i = 0; i < nn; i++) res[i] = int(res1[i] + res2[i]);
	for(int i = 0; i < n; i++) if(match(str[i], str[i+1])) res[i*2+1]--;
	int maxi = 0;
	for(int i = 0; i < nn; i++) maxi = max(maxi, res[i]);
	cout << maxi << endl;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}