Problem Description

You have a string of lowercase letters.You need to find as many sequence “gdCpc” as possible.But letters in the same position can only be used once。

 

 

Input

The input file contains two lines.

The first line is an integer n show the length of string.(1≤n≤2×105)

The second line is a string of length n consisting of lowercase letters and uppercase letters.

 

 

Output

The input file contains an integer show the maximum number of different subsequences found.

 

 

Sample Input


 

10 gdCgdCpcpc

 

 

Sample Output


 

2

 思路：前缀和，分成 c,xt,xtC,xtCp,xtCpc

#include<cstdio>
#include<cstring>
using namespace std;
char a[205000];
int falg=1;//xtCpc

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",a);
        /*for(int i=0;i<40000;i++) a[i]='x';
        for(int i=40000;i<80000;i++) a[i]='t';
        for(int i=80000;i<120000;i++) a[i]='C';
        for(int i=120000;i<160000;i++) a[i]='p';
        for(int i=160000;i<200000;i++) a[i]='c';
        a[200000]='\0';*/
        int sum[10]={0},s=0;
        for(int i=0;a[i]!='\0';i++)
        {
            if(a[i]=='x') sum[1]++;
            else if(a[i]=='t')
            {
                if(sum[1]>=1)
                {
                    sum[1]--;
                    sum[2]++;
                }
            }
            else if(a[i]=='C') {
                if(sum[2]>=1)
                {
                    sum[2]--;
                    sum[3]++;
                }
            }
            else if(a[i]=='p') {
                if(sum[3]>=1)
                {
                    sum[3]--;
                    sum[4]++;
                }
            }
            else if(a[i]=='c')
            {
                if(sum[4]>=1)
                {
                    sum[4]--;
                    sum[5]++;
                }
            }
        }
        //scanf("%s",a);
        printf("%d\n",sum[5]);
    }
}