34713번 - Collecting Sogang

문제

알파벳 소문자로 이루어진 문자열 $S$가 주어진다. 이 문자열에서 s, o, g, a, n, g 여섯 개의 문자를 문자열의 앞에서부터 순서대로 추출하여 sogang이라는 단어를 만들 수 있다. 이때, 이 여섯 개의 문자가 문자열에서 연속할 필요는 없다.

sogang단어를 완성할 때마다 상품 하나를 받는다. 사용된 문자는 문자열에서 제거되며, 제거된 자리의 뒷부분에 있는 문자들은 앞으로 당겨진다. 이 과정을 여러 번 반복할 때, 받을 수 있는 상품의 최대 개수를 구하시오.

입력

첫 번째 줄에 문자열의 길이에 해당하는 정수 $N$이 주어진다. (1ドル \le N \le 100,000円$)

두 번째 줄에는 알파벳 소문자로 구성된 길이가 $N$인 문자열 $S$가 주어진다.

출력

위의 규칙에 따라 단어를 만들 때, 받을 수 있는 상품의 최대 개수를 출력하여라.

제한

노트