CF2072B Having Been a Treasurer in the Past, I Help Goblins Deceive

After completing the first quest, Akito left the starting cave. After a while, he stumbled upon a goblin village. Since Akito had nowhere to live, he wanted to find out the price of housing. It is well known that goblins write numbers as a string of characters '-' and '\_', and the value represented by the string $ s $ is the number of distinct subsequences $ ^{\text{∗}} $ of the string $ s $ that are equal to the string "-\_-" (this is very similar to goblin faces). For example, the string $ s= $ "-\_--\_-" represents the number $ 6 $ , as it has $ 6 $ subsequences "-\_-": 1. $ s_1+s_2+s_3 $ 2. $ s_1+s_2+s_4 $ 3. $ s_1+s_2+s_6 $ 4. $ s_1+s_5+s_6 $ 5. $ s_3+s_5+s_6 $ 6. $ s_4+s_5+s_6 $ Initially, the goblins wrote a random string-number $ s $ in response to Akito's question, but then they realized that they wanted to take as much gold as possible from the traveler. To do this, they ask you to rearrange the characters in the string $ s $ so that the value of the number represented by the string $ s $ is maximized. $ ^{\text{∗}} $ A subsequence of a string $ a $ is a string $ b $ that can be obtained by deleting several (possibly $ 0 $ ) characters from $ a $ . Subsequences are considered different if they are obtained by deleting different sets of indices.

N/A

N/A

In the first test case, it is beneficial to rearrange the characters to form the string "-\_-". This is the only string of three characters that has at least one subsequence "-\_-". In the second test case, there is only one character "-", and at least two are needed for the subsequence "-\_-". This means that for any rearrangement of characters, the answer will be $ 0 $ . In the seventh and eighth test cases, the length of the string $ n < 3 $ , which means that subsequences of length $ 3 $ do not exist.