When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.

Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.

Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.

More formally, let's define the function vowel(c) which is equal to 1, if c is a vowel, and to 0 otherwise. Let s_{i} be the i-th character of string s, and s_{i}..j be the substring of word s, staring at the i-th character and ending at the j-th character (s_{is}_{i} + 1... s_{j}, i ≤ j).

Then the simple prettiness of s is defined by the formula:$\operatorname{simple}(s) = \frac{\sum_{i = 1}^{|s|} \operatorname{vowel}(s_{i})}{|s|}$

The prettiness of s equals $\sum_{1 \leq i \leq j \leq|s|} \operatorname{simple}(s_{i . . j})$

Find the prettiness of the given song title.

We assume that the vowels are I, E, A, O, U, Y.


-----Input-----

The input contains a single string s (1 ≤ |s| ≤ 5·10^5) — the title of the song.


-----Output-----

Print the prettiness of the song with the absolute or relative error of at most 10^{ - 6}.


-----Examples-----
Input
IEAIAIO

Output
28.0000000

Input
BYOB

Output
5.8333333

Input
YISVOWEL

Output
17.0500000



-----Note-----

In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.

Difficulty: HARD
Tags: String algorithms

Mathematics

Starter code:

Solutions:
ss = list(map(lambda c: c in 'IEAOUY', input()))
n = len(ss)
w = [0] * n
for i in range(1, n + 1):
	w[0] += 1 / i
w[n - 1] = w[0]
sigma = w[0]
for i in range(1, (n - 1) // 2 + 1):
	sigma -= 1 / i + 1 / (n + 1 - i)
	w[n - i - 1] = w[i] = w[i - 1] + sigma
ans = 0
for i in range(0, n):
	ans += ss[i] * w[i]
print(ans)


(m, t) = (0, [q in 'IEAOUY' for q in input()])
d = s = sum(t)
for k in range(len(t), 0, -1):
	m += d / k
	s -= t[k - 1] + t[-k]
	d += s
print(m)


from math import fsum

def main():
	(l, x) = ([0, 0], 0)
	for c in input():
		if c in ('I', 'E', 'A', 'O', 'U', 'Y'):
			x += 1
		l.append(x)
	n = l[-1]
	res = [float(n)]
	for m in range(2, len(l) - 1):
		n += l[-m] - l[m]
		res.append(n / m)
	print('{:.7f}'.format(fsum(res)))

def __starting_point():
	main()
__starting_point()


arr = []
for i in input():
	arr.append(i)
n = len(arr)
res = 0
add = [0] * (n + 10)
add[n] = 1 / n
for i in range(n - 1, 0, -1):
	add[i] = add[i + 1] + 1 / i
for i in range(n):
	if arr[i] in ['I', 'E', 'A', 'O', 'U', 'Y']:
		x = min(i, n - i - 1)
		y = max(i, n - i - 1)
		res += x + 1
		res += (x + 1) * (add[x + 2] - add[y + 1])
		res += (n + 1) * add[y + 1] - (n - y)
print(res)


word = input()
n = len(word)

def vowel(x):
	if x in ['A', 'E', 'I', 'O', 'U', 'Y']:
		return 1
	else:
		return 0
sums = [0] * n
sums[n - 1] = 1 / n
for k in range(n - 2, -1, -1):
	sums[k] = sums[k + 1] + 1 / (k + 1)

def numb(k):
	if k <= (n + 1) // 2:
		return (k + 1) * (sums[k + 1] - sums[n - k - 1]) + (n + 1) * sums[n - k - 1]
	else:
		return numb(n - k - 1)
res = 0
if n == 1:
	res = vowel(word[0])
elif n == 2:
	res = (vowel(word[0]) + vowel(word[1])) * 3 / 2
elif n == 3:
	res = (vowel(word[0]) + vowel(word[2])) * (1 + 1 / 2 + 1 / 3) + 7 / 3 * vowel(word[1])
else:
	for k in range(n):
		res += vowel(word[k]) * numb(k)
print('%.7f' % res)


s = input()
lst = [0]
for i in range(1, len(s) + 1):
	lst.append(lst[-1] + 1 / i)
x = lst[len(s)]
res = 0
for (i, j) in enumerate(s):
	if j in 'AEIOUY':
		res += x
	x += lst[len(s) - i - 1] - lst[i + 1]
print(res)


__author__ = 'PrimuS'
s = input()
n = len(s)
a = [0] * n
ps = [0] * n
for i in range(n):
	if s[i] in 'IEAOUY':
		a[i] = 1
ps[0] = a[0]
for i in range(1, n):
	ps[i] = ps[i - 1] + a[i]
import math
up = math.ceil((n - 1) / 2)
ss = [0] * up
prev = 0
for i in range(up):
	ss[i] = (a[i] + a[n - i - 1]) * (i + 1)
	if i == n - i - 1:
		ss[i] /= 2
	ss[i] += prev
	prev = ss[i]
res = 0
x = 0
res = ps[n - 1]
for i in range(2, n):
	k = n - i + 1
	cur = 0
	if k < i:
		cur += (ps[n - k] - ps[k - 2]) * k
		cur += ss[k - 2]
	else:
		cur += (ps[n - i] - ps[i - 2]) * i
		cur += ss[i - 2]
	res += cur / i
if n > 1:
	res += ps[n - 1] / n
print(res)


def sum_vowels(s, i, j):
	ans = 0
	for index in range(i, j + 1):
		if s[index] in 'AEIOUY':
			ans += 1
	return ans

def __starting_point():
	s = input()
	n = len(s)
	ans = 0
	num = 0
	den_inv = 0
	prev_sum = sum_vowels(s, 0, n - 1)
	for i in range(int(n / 2)):
		num += prev_sum
		den_inv = 1 / (i + 1) + 1 / (n - i)
		ans += num * den_inv
		if s[i] in 'AEIOUY':
			prev_sum -= 1
		if s[n - 1 - i] in 'AEIOUY':
			prev_sum -= 1
	if n % 2 == 1:
		i = int(n / 2)
		num += sum_vowels(s, i, i)
		den_inv = 1 / (i + 1)
		ans += num * den_inv
	print('{:.6f}'.format(ans))
__starting_point()


string = input().strip()
s = [0]
for c in string:
	s.append(s[-1] + (c in 'IEAOUY'))
(result, cur) = (0, 0)
for l in range(1, len(string) + 1):
	cur += s[-l] - s[l - 1]
	result += cur / l
print(result)


lst = [0] + [_ in 'IEAOUY' for _ in input()]
n = len(lst) - 1
for _ in range(1, n + 1):
	lst[_] += lst[_ - 1]
ans = 0
s = 0
for l in range(1, n // 2 + 1):
	s += lst[n - l + 1] - lst[l - 1]
	ans += s / l + s / (n - l + 1)
if n % 2:
	s += lst[n // 2 + 1] - lst[n // 2]
	ans += s / (n // 2 + 1)
print('%0.9f' % ans)


from itertools import accumulate
vowels = set('AIUEOY')
s = input()
n = len(s)
vs = list(accumulate((0 if i == 0 else 1 / i for i in range(n + 1))))
r = 0
v = 0
for i in range(n):
	v += vs[n - i] - vs[i]
	if s[i] in vowels:
		r += v
print(r)


i = input()
l = len(i)
run = [0] * (l + 1)
for a in range(1, l + 1):
	if i[a - 1] in ['A', 'E', 'I', 'O', 'U', 'Y']:
		run[a] = run[a - 1] + 1
	else:
		run[a] = run[a - 1]
tot = 0
fore = 0
for i in range(1, l + 1):
	fore -= 1 / i
ey = [fore] + [0] * l
for i in range(1, l + 1):
	ey[i] = ey[i - 1] + 1 / (l + 1 - i) + 1 / i
for i in range(1, l + 1):
	tot += ey[i] * run[i]
print(tot)


song = input()
le = len(song)
su = 0
for x in range(1, le + 1):
	su += 1 / x
l = [0] * le
l[0] = su
diff = su
for x in range(1, int((le + 1) / 2)):
	diff -= 1 / x + 1 / (le + 1 - x)
	l[x] = l[x - 1] + diff
for x in range(int((le + 1) / 2), le):
	l[x] = l[le - 1 - x]
ans = 0
for x in range(le):
	let = song[x]
	if let in ['A', 'E', 'I', 'O', 'U', 'Y']:
		ans += l[x]
print(ans)


def main():
	s = read(0)
	m = [1 if i in 'AEIOUY' else 0 for i in s]
	n = len(m)
	m1 = [0]
	m2 = [0]
	for i in range(n):
		m1.append(m1[-1] + 1 / (1 + i))
		m2.append(m2[-1] + 1 / (n - i))
	mlast = m1[-1]
	for i in range(1, n + 1):
		m1[i] = m1[i - 1] + m1[i]
		m2[i] = m2[i - 1] + m2[i]
	sm = 0
	for i in range(n):
		sm += m[i] * ((i + 1) * mlast - m1[i] - m2[i])
	print(sm)

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')
write(main())


def main():
	s = input()
	n = len(s)
	b = [1.0 / (i + 1) for i in range(n)]
	d = [(n - i) / (i + 1) for i in range(n)]
	d = d[::-1]
	for i in range(1, n):
		b[i] += b[i - 1]
		d[i] += d[i - 1]
	res = 0.0
	for i in range(n):
		if not (s[i] == 'I' or s[i] == 'E' or s[i] == 'A' or (s[i] == 'O') or (s[i] == 'U') or (s[i] == 'Y')):
			continue
		z = [i + 1, n - i]
		z.sort()
		res += z[0] * (b[z[1] - 2] - b[z[0] - 1] + 1) + d[z[0] - 1]
	if len(s) == 1 and res > 0:
		res -= 1
	print(res)
main()