Magnus
면접 대비시간 제한1초메모리 제한512 MB
길이 N의 대문자 단어에서 원하는 글자를 삭제해 남긴 글자에 겹치지 않는 부분 수열 "HONI"가 최대한 많이 나오게 하고 그 개수를 출력합니다.
문제
Magnus는 Kile에게 체스 게임에서 패배한 뒤, 경쟁 프로그래밍에서 위로를 찾았다. 얼마 지나지 않아 그는 유명한 COCI 대회를 알게 되었고, 그곳에서 운을 시험해 보기로 마음먹었다.
그는 Kile에게 메일을 보냈다. "Kile, 부탁이야. 나를 COCI에 대비시켜 줘. Magnus."
Kile이 답장했다. "COCI에 참가하고 싶다고? 좋아, 몸풀기 문제를 주지. 어떤 단어에서 연속한 네 글자가 부분 단어 "HONI"(COCI의 크로아티아어 약자)를 이루는 것을 HONI-블록이라고 부른다. 내가 길이 N인 단어를 보내면, 네가 원하는 만큼 글자를 지워서(하나도 지우지 않아도 된다) 최종 단어에 HONI-블록이 최대한 많이 남도록 해라. Kile."
Magnus는 매우 걱정되어 COCI 경쟁 무대에 도움을 청했다. 그가 최종 단어에서 얻을 수 있는 HONI-블록의 최대 개수를 구하자.
입력
첫째 줄에 길이 N(1 ≤ N ≤ 100 000)인 단어가 주어진다. 단어는 영어 대문자로만 이루어져 있다.
출력
첫째 줄에 HONI-블록의 최대 개수를 출력한다.