크리스 마틴

미친 과학자 창호는 어젯밤 구재현을 납치해 구재현의 DNA를 추출했다. 사람의 DNA는 길이가 $n$이고, A, C, G, T 네 종류의 염기로 이루어져 있다.

창호는 늘 자신을 놀리던 구재현보다, 잘생긴 콜드플레이의 크리스 마틴을 더 좋아한다. 이 취향을 바탕으로 창호는 다음 이론을 세웠다. 구재현의 DNA와의 유사도가 가장 낮은 DNA가 바로 크리스 마틴의 DNA다.

두 DNA의 유사도는 두 DNA의 최장 공통 부분 수열(LCS)의 길이로 정의한다. 어떤 DNA의 부분 수열이란 그 DNA에서 염기를 0개 이상 지워서 얻는 DNA이며, 두 DNA의 최장 공통 부분 수열은 두 DNA 모두의 부분 수열이면서 길이가 가장 긴 수열이다.

사실 지금 여러분도 창호에게 납치되어 있다. 크리스 마틴의 DNA를 찾지 못하면 무슨 일이 벌어질지 모른다. 구재현의 DNA가 주어질 때, 길이가 같은 모든 DNA 중에서 구재현의 DNA와의 유사도가 최소가 되는 값을 구하자. 즉, 길이 $n$인 임의의 DNA $T$에 대해 유사도(LCS의 길이)가 가질 수 있는 최솟값을 출력하면 된다.

첫째 줄에 사람 DNA의 길이 $n$이 주어진다. ($1 \le n \le 10000$)

둘째 줄에 길이 $n$인 DNA 문자열이 주어진다. 문자열의 각 문자는 A, C, G, T 중 하나다.

첫째 줄에 가능한 최소 유사도를 출력한다. 즉, 주어진 DNA와 길이 $n$인 임의의 DNA 사이의 최장 공통 부분 수열 길이의 최솟값을 출력한다.