In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4, Ultra-QuickSort produces the output 0 1 4 5 9. Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input Format

The input contains several test cases. Every test case begins with a line that contains a single integer (n<500,000) -- the length of the input sequence. Each of the following n lines contains a single integer ( 0≤a[i]≤999,999,999), the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output Format

For every input sequence, your program print a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Example

Input

5
9
1
0
5
4
3
1
2
3
0

Output

6
0

Problem Analysis

Merge Sort, Math

Code Implementation

#include <iostream>
using namespace std;
using LL = long long;
const int N = 5e5 + 10;

int n, idx;
LL a[N], t[N];
int solve(int left, int right) {
    int cnt = 0;
    if(left >= right) return cnt;
    int mid = ((right - left) >> 1) + left;
    cnt += solve(left, mid) + solve(mid + 1, right);
    int l = left, r = mid + 1, ix = 0;
    while(l <= mid && r <= right) {
        if(a[l] <= a[r]) t[ix++] = a[l++];
        else t[ix++] = a[r++], cnt += mid - l + 1;
    }
    while(l <= mid) t[ix++] = a[l++];
    while(r <= right) t[ix++] = a[r++];
    for(int i = left, j = 0; i <= right; ++i) a[i] = t[j++];
    return cnt;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1) {
        idx = 0;
        cin >> n;
        if(!n) break;
        while(n--) cin >> a[idx++];
        cout << solve(0, idx - 1) << '\n';
    }
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status