Steven the monkey recently discovered something called the monkey stock market. He is given an array of integers. Each integer denotes the price of one stock share on the day. On each day he can:
- Spend all his money to buy stock shares. He gains shares, where denotes the amount of money he has. Then becomes .
- Sell all the shares he currently has. He gains dollars, where denotes the number of shares he has. Then becomes .
- Don't take action.
Being an extremely popular monkey influencer, he can control the stock market by reordering the stock prices any way he wants.
However, he is an extremely busy monkey, so he hires you to help him determine an order of the prices such that if he acts optimally, he can maximize the amount of money he has by the end of the days. Given that he starts with no stocks and an undetermined amount of money, output a list of directions as to which days he should buy, sell or skip on.
The first line contains the integer , the number of days.
The next line contains the space-separated integers .
On the first line, output some optimal permutation of the original array. On the next line, output letters without spaces in between — the letter denoting the action performed on the day, which is either
B for buying,
S for selling, or
E for skipping. Remember that having shares is not the same as having money.
Note: Any valid output will be accepted.
3 4 2 2
2 2 4 BES
Say we start with dollars. We first buy, so we end up with stocks. On the second day, we skip, and on the last day, we sell to obtain a total of dollars. This arrangement can be proven to be optimal.