You recently purchased a CD player from Bob's Bargain Barn. As you don't like listening to songs from your CDs in the same order every day, you were very interested in the "Random" button on the CD player. According to the instruction manual, if the CD player has n songs, the "Random" feature works as follows:
Based on this algorithm, for 3 songs you could legally obtain "ABCCAB" and "BCABCA", but not "AABBCC".
- Randomly select a permutation of the n songs.
- Play the songs in order from that permutation.
- Go to step 1.
You are not sure if you trust Bob's Bargain Barn, so you want to figure out if the CD player is broken or not. However, as luck would have it, your sister had started listening to the CD, so you don't know when the next permutation begins. This means that the list "BBAC" could be an acceptable list, if the first B was the last song in the first permutation, and the second B started the second permutation.
You will be given a String songlist containing the list of songs that you heard. Each distinct character in songlist represents a single distinct song. This should be concatenated to form one String. You will also be given n, the number of songs on your CD. If the entire songlist could have been generated using the above algorithm, return the earliest 0-based index in songlist where a new permutation began. If there are multiple valid indices that could be the start of a permutation, return the smallest of these. If the songlist could not have been generated by the algorithm described above, return -1. See the examples for clarification.