Code Generator

borisal National High School Prog...
Limits 500ms, 512 MB

Disha has a string $S$. In one second, Disha can choose a subsequence from $S$ that make the word “code” and remove it from the string. The process will be continued until she can't choose a subsequence that make the word.

In this problem, Good letter means [c,d,e,o]. And others letters are Bad.

Now, you have to find the maximum number of seconds Disha will work.

Input

The first line of the input contains a single integer $n$- the length of the string $s$.
Next line contains string $s$. the string consists of only lowercase English letters.

Constraints

Subtask 1 (10 points)

$1 \le n \le 5000$

Subtask 2 (30 points)

$1 \le n \le 500000$
Number of good letters $\leq 5000$

Subtask 3 (60 points)

$1 \le n \le 500000$

Output

Output the maximum number of seconds Disha will work.

Sample

InputOutput
8
codceode
2

Submit

Login to submit.

Statistics

52% Solution Ratio
Tahmid690Earliest, Jun '20
riyad000Fastest, 0.0s
ITisMAHMUDLightest, 131 kB
bokaifShortest, 132B
Toph uses cookies. By continuing you agree to our Cookie Policy.