Problem Background

Magnus lost a game of chess to Kile and became obsessed with programming. He decided to try his luck at the COCI competition.

Upon learning that Magnus wanted to participate in COCI, Kile gave him this warm-up problem.

Problem Description

Given a word of length $N$. Remove any number of letters from the word to form as many instances of HONI as possible.

Input Format

Input consists of a string of length $N$ containing only English letters, representing the given word.

Output Format

Output the maximum number of HONI sequences that can be formed.

Sample Input and Output

Sample Input #1

MAGNUS

Sample Output #1

0

Sample Input #2

HHHHOOOONNNNIIII

Sample Output #2

1

Sample Input #3

PROHODNIHODNIK

Sample Output #3

2

Notes

Sample 2 Explanation

You can delete the first three occurrences of each letter H, O, N, and I from the original word to get HONI.

Data Size and Constraints

For $100\%$ of the data, $1 \le N \le 10^5$.

Note

This problem's score is set according to the original COCI problem, with a maximum score of $50$.

The problem is translated from COCI2018-2019 CONTEST #3 T1 Magnus.

见题面 Input 部分

见题面 Output 部分