BaoBao has just found a stringsof lengthnconsisting of 'C' and 'P' in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substringsisi+1si+2si+3 of sis "good", if and only if si=si+1=si+3='C' ,and si+2='P',where sidenotes the i-th character in string s. The value of sis the number of different "good" substrings in s. Two "good" substringssisi+1si+2si+3andsjsj+1sj+2sj+3are different ,if and onlyi≠j. To make this string more valuable, BaoBao decides to buy some characters from a character store. Each time he can buy one 'C' or one 'P' from the store, and insert the character into any position ins.But everything comes with a cost. If it's the i-th time for BaoBao to buy a character, he will have to spend i - 1units of value. The final value BaoBao obtains is the final value ofs minus the total cost of all the characters bought from the store. Please help BaoBao maximize the final value.
BaoBao has just found a string s of length n consisting of 'C' and 'P' in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substring sisi+1si+2si+3 of s is "good", if and only if si=si+1=si+3= 'C' ,and si+2='P', where si denotes the i-th character in string s. The value of s is the number of different "good" substrings in s. Two "good" substrings sisi+1si+2si+3 and sjsj+1sj+2sj+3 are different ,if and only i ≠ j . To make this string more valuable, BaoBao decides to buy some characters from a character store. Each time he can buy one 'C' or one 'P' from the store, and insert the character into any position in s.But everything comes with a cost. If it's the i-th time for BaoBao to buy a character, he will have to spend i - 1 units of value. The final value BaoBao obtains is the final value of s minus the total cost of all the characters bought from the store. Please help BaoBao maximize the final value.
