ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1393. Average Common Prefix

Time limit: 1.5 second
Memory limit: 16 MB
Let T denote some string of length n consisting of capital Latin letters. Let Shift(T, k) denote the left cyclic shift of T by k-1 positions. The permutation array for T is an array P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order.
For given two strings v and w we define LCP(v, w) as the length of their longest common prefix. The Average LCP of the string T is the average length of longest common prefix between two consecutive shifts:
Problem illustration
Example. T = 'MISSISSIPPI', n = 11:
i P[i] Shift(T, P[i]) LCP
1 11 'IMISSISSIPP' 1
2 8 'IPPIMISSISS' 1
3 5 'ISSIPPIMISS' 4
4 2 'ISSISSIPPIM' 0
5 1 'MISSISSIPPI' 0
6 10 'PIMISSISSIP' 1
7 9 'PPIMISSISSI' 0
8 7 'SIPPIMISSIS' 2
9 4 'SISSIPPIMIS' 1
10 6 'SSIPPIMISSI' 3
11 3 'SSISSIPPIMI'  
Average LCP of 'MISSISSIPPI' is 1.3

Input

The first line of the input contains integer n (1 < n < 250001). The second line contains string T.

Output

The only line of the output should contain the Average LCP of T with at least 3 digits after the decimal point.

Sample

inputoutput
11
MISSISSIPPI
1.300
Problem Author: Ilya Grebnov