Description

You are given a word of length $N$. Delete any number of letters from the word so that you can form as many HONI as possible.

Input Format

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

Output Format

Output the maximum number of HONI that can be formed.

MAGNUS

0

HHHHOOOONNNNIIII

1

PROHODNIHODNIK

2

Hint

Explanation of Sample 2

You can delete the earliest $3$ occurrences of each of the four letters H, O, N, I from the original word to obtain HONI.

Constraints

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

Notes

The score of this problem follows the original COCI setting, with a full score of $50$.

Translated from COCI2018-2019 CONTEST #3 T1 Magnus.

Translated by ChatGPT 5