ForkliftTruckOperator

Bob has a very interesting job: he is a forklift truck operator. Today he is facing the following problem at work.

There are initially N pallets placed in a row from the left to the right and numbered starting from 0. Each pallet contains exactly one box on top of it. There are two types of boxes: red boxes and blue boxes. Each red box has height 1 and each blue box has height exactly sqrt(2).

In a single move, Bob can choose some consecutive set of pallets and, using a forklift truck, lift up all boxes from the set and put them down on top of some other consecutive set of pallets. (Note that when one box is placed on top of another box, the height of the resulting stack is precisely equal to the sum of heights of both boxes.) More formally, in a single move Bob can do the following four steps (in the given order):

1. Choose any non-empty consecutive set of pallets. (I.e., pallets with indices from A to B, inclusive, for some A and B.) Bob is going to lift up the stacks of boxes that are currently placed on these pallets.
2. Choose any non-empty consecutive set of pallets disjoint with the first set. The number of pallets must be the same as in the first set. Additionally, the stacks of boxes on the pallets that were selected in this step must all have exactly the same height. Bob is going to place the stacks he lifted in step 1 onto these stacks.
3. Bob moves the stacks of boxes from the first set of pallets onto the stacks of boxes on the second set of pallets. Note that the order of stacks must be preserved. E.g., if he lifted up stacks of boxes from pallets 2-4 and now he wants to place them onto pallets 6-8, stack from pallet 2 goes onto pallet 6, and so on.
4. After the move, all empty pallets are removed. The remaining pallets are pushed together and then renumbered starting from 0.

The height of a pallet is defined as the sum of heights of boxes placed on it. To avoid unnecessary chaos, Bob decided that after each move there should be at most two different pallet heights. In other words, there must never be any three pallets with three different heights.

You are given a String pallets which contains N characters. For each valid i, the i-th character of pallets is 'R' if initially the box on the i-th pallet is a red box, and 'B' if it is a blue one. Bob's task is to find some sequence of moves such that after executing all moves from this sequence there would be exactly one pallet left with all the initial boxes placed on top of it (in any order). Return the minimum possible size of such sequence. If such sequence doesn't exist, return -1 instead.