原始题目

File Name

• time limit per test1 second
• memory limit per test256 megabytes
• inputstandard input
• outputstandard output

You can not just take the file and send it. When Polycarp trying to send a file in the social network "Codehorses", he encountered an unexpected problem. If the name of the file contains three or more "x" (lowercase Latin letters "x") in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed.

Determine the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. Print 0 if the file name does not initially contain a forbidden substring "xxx".

You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by 1. For example, if you delete the character in the position 2 from the string "exxxii", then the resulting string is "exxii".

Input

The first line contains integer n (3≤n≤100) — the length of the file name.

The second line contains a string of length n consisting of lowercase Latin letters only — the file name.

Output

Print the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. If initially the file name dost not contain a forbidden substring "xxx", print 0.

Examples

Input

6
xxxiii

Output

1

Input

5
xxoxx

Output

0

Input

10
xxxxxxxxxx

Output

8

Note

In the first example Polycarp tried to send a file with name contains number 33, written in Roman numerals. But he can not just send the file, because it name contains three letters "x" in a row. To send the file he needs to remove any one of this letters.

题目大意

文件名中超过n个（n>=3）连续的x时需要修改n-2次。

解题思路

每次贪心的取最大连续个x值，然后判断累加即可。

#解题代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define eps 1e-8
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return a?gcd(b%a,a):b;
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
 } 

int n,m,vis[maxn],ans[maxn],cnt;
char a[maxn];
int main()
{
	while(~scanf("%d",&n))
	{
		getchar();
		cnt=0;
		int ccnt=0;char temp;
		gets(a);
		for(int i=0;i<n;i++)
		{
			if(a[i]=='x') ccnt++;
			else
			{
				if(ccnt>=3) cnt+=ccnt-2;
				ccnt=0;
			} 
		}
		if(ccnt>=3) cnt+=ccnt-2;
		printf("%d\n",cnt);
	} 
 } 

收获与反思

字符串简单贪心