Paper Folding

There is a long strip of paper of length N cm and width 1 cm. The strip is divided into N unit squares. Both sides of every square are colored either red or blue, and the two sides of the same square always have different colors.

You want to fold the strip several times so that its final length is as short as possible. In one fold, choose a positive integer K smaller than the current strip length. At the point K cm from the left edge, lift the part to the left of that point and fold it firmly onto the part to the right. During the fold, any two faces that are pressed together must have different colors.

The diagram below shows one possible folding sequence.

Find one sequence of folds that makes the final strip length minimum.

The first line contains an integer N, the length of the strip. (2 <= N <= 10000)

The second line contains a string of length N. Each character is either c or p; the i-th character gives the color of the upper side of the i-th square from the left. The character c denotes red, and p denotes blue.

On the first line, print the minimum possible length of the strip after all folds.

On the second line, print the number of folds M.

If M > 0, print M integers on the third line, separated by spaces. The i-th integer is the value K chosen for the i-th fold.

If there are multiple optimal folding sequences, you may output any one of them.