e-olymp
Змагання

Дерево Фенвика

Це вбивство!

Одного разу детектив Сайкат розслідував справу про вбивство. На місці злочину він виявив сходи, на кожній сходинці яких було записано одне число. Він знайшов це підозрілим і вирішив запам'ятовувати всі пройдені числа. Пам'ятаючи пройдені числа, він виявив у них закономірність. Детектив вирішив для кожного числа на сходах записати суму усіх чисел, які він раніше спостерігав на сходах, і які менші за записане на поточній сходинці. Знайти суму всіх чисел, записаних у щоденнику детектива.

Вхідні дані

Перший рядок містить кількість тестів t (t10). Далі йдуть 2t рядків. Перший рядок задає кількість сходинок n (1n105). Наступний рядок містить n чисел, записаних на сходинках. Усі записані числа змінюються від 0 до 106.

Вихідні дані

Для кожного тесту вивести в окремому рядку підсумкову суму.

Ліміт часу 1 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1
5
1 5 3 6 4
Вихідні дані #1
15