B - Abbreviate Fox Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の英小文字のみからなる文字列 s が与えられます。 すぬけ君は s から fox という部分文字列を 1 つ選んで取り除き、その前後の部分を連結する、という操作を何度でも行うことができます。

すぬけ君が操作を何度か行ったあと、s の長さは最小でいくつになりえますか？

制約

  • 1 \leq N \leq 2 \times 10^{5}
  • s は英小文字のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
s

出力

すぬけ君が操作を何度か行ったあとの s の長さとしてありうる値の最小値を出力せよ。

入力例 1

6
icefox

出力例 1

3
  • icefox の末尾 fox を取り除くことで s を ice にすることができます。

入力例 2

7
firebox

出力例 2

7
  • fox という部分文字列が存在しません。

入力例 3

48
ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo

出力例 3

27

Score : 400 points

Problem Statement

Given is a string S of length N consisting of lowercase English letters. Snuke can do this operation any number of times: remove fox occurring as a substring from s and concatenate the remaining parts of s.

What is the minimum possible length of s after some number of operations by Snuke?

Constraints

  • 1 \leq N \leq 2 \times 10^{5}
  • s is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
s

Print

Print the minimum possible length of s after some number of operations by Snuke.

Sample Input 1

6
icefox

Sample Output 1

3
  • By removing the fox at the end of icefox, we can turn s into ice.

Sample Input 2

7
firebox

Sample Output 2

7
  • fox does not occur as a substring.

Sample Input 3

48
ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo

Sample Output 3

27