You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在线性代数中，逆序数是与排列有关的一个概念。对于一个给定的排列，逆序数是指在该排列中，所有较大的数位于较小数前面的对数目的总和。逆序数不仅在理论数学中有应用，在计算机科学中的排序算法和数据结构分析等领域也非常有用。通过分析逆序数，可以了解排列的特性，如奇偶性，以及在某些算法中预测算法性能。

题目描述

由于小李同学整天网瘾，影响了课程学习，甚至不会找逆序数。可是很不幸的是老师在课上抽到了小李同学，让他起来回答问题，刚好就是一道关于逆序数的问题。现在请编程高手的你来设计一个程序，帮助小李解决老师的问题。

输入

一次输入包括多个测试用例。

每个测试用例的第一行输入整数 n，代表该用例中输入序列的长度。 接下来 n 行每行输入一个整数 aᵢ,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。

当输入用例中包含的输入序列长度为 0 时，输入终止，该序列无需处理。

输出

对于每个需要处理的输入序列，输出一个整数，代表对给定输入序列的逆序数，每个整数占一行。

样例

5
9
1
0
5
4
3
1
2
3
0

6
0

数据范围

0≤n<500000,一个测试点中，所有 n 的和不超过 500000。0≤aᵢ≤999999999。

每个测试用例时间限制1s，内存限制256MB。