Status

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

42.1% (8/19)

Description

在某個星球上，他們的生命是由「な NA」組成，然而這個「な NA」可以用一個字串來表示，且這個字串中只有包含大寫的 $\text{A}$, $\text{T}$, $\text{C}$, $\text{G}$ 四個字母，然而這個字母會對特定的字母產生吸引力，$\text{A}$ 與 $\text{T}$ 會互相吸引、$\text{C}$ 與 $\text{G}$ 會互相吸引，每對相互吸引的字母會產生 $1$ な的吸引力。

雖然我們可以用字串表示「な NA」，但是「な NA」在三維空間中會扭曲，由於字母間還會互相吸引，所以有可能對折 $180^\circ$，如以下示意圖：
對於字串「CCAGTCGTTAACAAACTGACA」可能會因字母間的吸引力而對折。

在這裡我們先不考慮太複雜的三維扭曲，我們只考慮對折。

「な NA」的對折有以下的特徵：

將字串切兩刀，共分成三個子字串。
這三個子字串分別稱做 $L, M, R$，每個長度至少為 $1$

兩個字母在符合以下條件的時候會產生吸引力：

分別屬於字串 $L$ 與字串 $R$
$\text{A}$ 與 $\text{T}$ 會互相吸引、$\text{C}$ 與 $\text{G}$ 會互相吸引
與子字串 $M$ 的最短距離一樣 (最短距離就是 $L$ 中的字母與 $M$ 最左端的距離，$R$ 中的字母與 $M$ 最右端的距離)

請問給定一個「な NA」，請你找出適當的 $L$、$M$、$R$ ，產生最多な的吸引力？

Input Format

輸入包含兩行，第一行只有一個整數 $N$，代表な NA 的字串長度，
接下來第二行有 $N$ 個字元 $c_i$，代表な NA 的字串。

$3\leq N \leq 2\cdot 10^5$
$c_i \in \{ `\text{A'}, `\text{T'}, `\text{C'}, `\text{G'} \}$

Output Format

輸出有一行，包含一個整數為最多會產生な的吸引力。

Sample Input 1

21
CCAGTCGTTAACAAACTGACA

Sample Output 1

Hints

字串:  CCAGTCGTTAACAAACTGACA
L字串: CCAGTCGTT
M字串:          A
R字串:           ACAAACTGACA

紅色為互相吸引的字母，且產生 $1$ な的吸引力。

對於上述範例來說，在 $L$ 字串中與 $M$ 字串距離為 $6$ 的字母 $`\text{G'}$，可與在 $R$ 字串中與 $M$ 字串距離為 $6$ 的字母 $`\text{C'}$ 形成吸引力。

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0~7	$N \leq 100$	0
2	0~17	$N \leq 5000$	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1 2
1	1000	65536	65536	1 2
2	1000	65536	65536	1 2
3	1000	65536	65536	1 2
4	1000	65536	65536	1 2
5	1000	65536	65536	1 2
6	1000	65536	65536	1 2
7	1000	65536	65536	1 2
8	1000	65536	65536	2
9	1000	65536	65536	2
10	1000	65536	65536	2
11	1000	65536	65536	2
12	1000	65536	65536	2
13	1000	65536	65536	2
14	1000	65536	65536	2
15	1000	65536	65536	2
16	1000	65536	65536	2
17	1000	65536	65536	2

Submit