Help me sort my socks! I have a pile of clean socks that I want to sort into pairs. Unfortunately, I can only take socks from either end of the pile, not the middle. Further, I can only remove socks from the pile a matching pair at a time. My strategy is to first split the pile into one or more smaller piles. I think some examples will make this clear. I'll represent each sock as a positive integer (matching integers indicate equal socks).

If the initial pile of socks is

1 2 3 3 2 1


then I don't have to do any splitting. I can remove both 1 socks, then both 2 socks, then both 3 socks.

If instead the initial pile is

1 2 3 2 3 1


then I have to split it first because I won't be able to pair all the socks by just removing them from the end. One possibility is to split it into the two piles

1 2 3 and 2 3 1


Now I can remove the 1 socks, leaving 2 3 and 2 3, followed by the 3 socks, leaving 2 and 2, and finally the 2 socks.

Your Job

Given the initial pile of socks, write a program that will split it into smaller piles that will allow me to sort the socks. Your program should split the pile into the fewest number of piles possible (if there are multiple best solutions, you need only find one). 

The input will be given as a list, delimited string, or other convenient form. It will contain only integers between 1 and some maximum value n, with each integer occurring exactly twice.

The output should consist of the input list split into smaller lists, given in any convenient form.

Examples

Input             Sample Output
1 1               1 1
1 2 1 2           1; 2 1 2
1 3 2 4 3 2 1 4   1 3 2; 4 3 2 1 4
1 2 3 4 3 4 1 2   1; 2 3; 4 3 4 1 2
1 1 2 2 3 3       1 1 2; 2 3 3
4 3 4 2 2 1 1 3   4 3 4 2; 2 1 1 3


Note that this isn't the only allowed output for most of these inputs. For the second case, for example, the outputs 1 2; 1 2 or 1 2 1; 2 would also be accepted.

Thanks to Sp3000 for some test suggestions!

I hate spending a long time sorting my clothes, so make your code as short as possible. Shortest answer in bytes wins!

Notes


I don't want to have to look behind a sock to see if its matching pair is there, so taking both socks in a pair from the same end is not allowed. E.g. if the pile is 1 1 2 2 then you wouldn't be able to leave it as one pile and take both 1 socks from the left end.
Pyth, 25 bytes

hf!u #-R.-F{BhMs_BMGGT)./


Test suite

Explanation:

hf!u #-R.-F{BhMs_BMGGT)./
                       ./    Form all partitions (implicitly) of the input.
 f                           Filter the permutations on
   u                 T)      Run the following function on the partition
                             until it reaches a fixed point:
                _BMG         Bifurcate the lists on reversal
               s             Concatenate
             hM              Take the first element of each list. 
                             These elements are all the ones on the ends of lists.
           {B                Bifurcate on deduplication
        .-F                  Bagwise subtraction.
                             Only elements repeated in ends of lists remain.
      -R            G        Remove these elements from each list.
   ' #'                      Filter out empty lists.
  !                          Negate. Only an empty list as fixed point succeeds.
h                            Output the first successful partition.