겹치는 구간

길이 $N$의 문자열 $S$가 주어진다. 문자열은 알파벳 소문자로 구성되어 있다.

$K$개의 구간 $[l_1,r_1],[l_2,r_2],\ldots,[l_K,r_K]$를 고르려고 한다. 고른 구간들은 다음 조건을 모두 만족해야 한다.

• $1 \le l_i < r_i \le N$ ($1 \le i \le K$).
• $l_1,l_2,\ldots,l_K,r_1,r_2,\ldots,r_K$는 모두 서로 다르다.
• $S_{l_i}=S_{r_i}$ ($1 \le i \le K$).
• $K=1$이면 $l_1<r_1$이다.
• $K\ge 2$이면 $l_1<l_2<r_1$, $l_K<r_{K-1}<r_K$이고, $l_i<r_{i-1}<l_{i+1}<r_i$ ($2 \le i \le K-1$)이다.

즉, $K\ge 2$일 때 끝점들은 다음과 같이 번갈아 나타난다.

예를 들어, $S=\text{abacbdcd}$이면 아래와 같이 $4$개의 구간을 고를 수 있다.

조건을 만족하도록 고를 수 있는 $K$의 최댓값을 구하여라. 조건을 만족하는 구간을 하나도 고를 수 없다면 답은 $0$이다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $S$

첫째 줄에 조건을 만족하도록 고를 수 있는 구간 개수의 최댓값을 출력한다.

• $1 \le N \le 2\,000$.
• $S$는 알파벳 소문자로만 이루어진 길이 $N$의 문자열이다.