Magic Towers
Easy
Execution time limit is 5 seconds
Runtime memory usage limit is 64 megabytes
Given a number n and a sequence of n numbers, your task is to examine all possible cyclic shifts of the sequence, sort them in lexicographical order, and then output them in this sorted order. If two cyclic shifts are identical, the one that starts earlier in the sequence is considered smaller.
Input
The input consists of no more than 200 test cases. Each test case is described over two lines. The first line contains an integer 1 ≤ n ≤ 50000, which represents the length of the sequence. The second line contains n numbers, each ranging from 0 to 100, representing the sequence itself. The input ends with a line containing the number 0 instead of n.
Output
For each test case, output a single number: the required sum.
Examples
Input #1
Answer #1
Submissions 60
Acceptance rate 17%