Background

Magnus lost to Kile in chess, so he became obsessed with programming. He decided to go to the COCI contest to try his luck.

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

Problem 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