#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r){
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r){
if (q[i] <= q[j]) tmp[k ++] = q[i ++];
else{
tmp[k ++] = q[j ++];
res += mid - i + 1;
}
}
while (i <= mid) tmp[k ++] = q[i ++];
while (j <= r) tmp[k ++] = q[j ++];
for (int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
return res;
}
int main(){
while (scanf("%d", &n) && n){
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
printf("%lld\n", merge_sort(0, n - 1));
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define lowbit(x) -x&x
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int tr[N];
int ans[N];
struct cow{
int s, e;
int idx;
bool operator <(const cow& t) const{
return e > t.e || (e == t.e && s < t.s);
}
}cows[N];
void add(int i, int z){
for (; i < N; i += lowbit(i))
tr[i] += z;
}
int ask(int i){
int res = 0;
for (; i; i -= lowbit(i))
res += tr[i];
return res;
}
int main(){
while (scanf("%d", &n) && n){
for (int i = 0; i < n; i ++ ){
int s, e;
scanf("%d%d", &s, &e);
s ++ ;
cows[i].s= s;
cows[i].e = e;
cows[i].idx = i;
}
sort(cows, cows + n);
memset(ans, 0, sizeof ans);
memset(tr, 0, sizeof tr);
ans[cows[0].idx] = 0;
add(cows[0].s, 1);
for (int i = 1; i < n; i ++ ){
if (cows[i].s == cows[i - 1].s && cows[i].e == cows[i - 1].e)
ans[cows[i].idx] = ans[cows[i - 1].idx];
else ans[cows[i].idx] = ask(cows[i].s);
add(cows[i].s, 1);
}
for (int i = 0; i < n; i ++ )
printf("%d ", ans[i]);
puts("");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define lowbit(x) -x&x
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mo = 100000007;
int n, casei;
int tr[N];
void add(int i, int z){
for (; i < N; i += lowbit(i))
tr[i] += z;
}
int ask(int i){
int res = 0;
for (; i; i -= lowbit(i))
res += tr[i];
return res;
}
LL mod(LL a, int b){
return (a % b + b) % b;
}
int main(){
int T;
scanf("%d", &T);
while (T -- ){
LL ans = 0;
memset(tr, 0, sizeof tr);
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
int x;
scanf("%d", &x);
int l = ask(x);
add(x, 1);
int r = (n - x) - (i - 1 - l);
ans += (LL)r * (r - 1) / 2 - (LL)l * r;
ans = mod(ans, mo);
}
printf("Case #%d: %lld\n", ++ casei, ans);
}
return 0;
}