Wyznacz liczbe inwersji w ciagu

witam,
Zaprezentuje treść mojego zadania:

Dany jest ciąg liczb. Inwersją w ciągu nazywamy każdą taką parę liczb i-tą i j-tą, że i>j oraz wartość i-tej jest mniejsza niż wartość j-tej.
Dla danego ciągu liczb wyznacz w nim liczbej inwersji.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita d (1 <= d <= 100), która oznacza liczbę zestawów dnych.
Każdy zestaw z dwóch linii. W pierwszej znajduje się liczba n (1<=n<=10000), oznaczająca liczbę liczb w ciągu.
W drugiej znajduje się n liczb z przedziału od -1000 do 1000, które oznaczają kolejne elementy ciągu.

Wyjście

Na wyjściu należy dla każdego zestawu danych wypisać jedną liczbę, oznaczającą liczbę inwersji w ciągu.

Przykład

Wejście:
2
5
1 2 3 1 5
4
4 3 2 1

Wyjście:
2
6

Może moje pytanie zamieściłem na złym forum, ale nie rozumiem polecenia. Rozumiem, że mamy dwa indeksy 'i' oraz 'j', czyli tak jak w bubble sort, mam przechodzić po ciągu "parami" od lewej i sprawdzać czy spełniony jest warunek wartość_i<wartość_j
Rozpisując do dla przykładu nr.1 z w/w treści:

1 2 3 1 5

j=0 i=1 (tutaj wartość i > wartość j) czyli ++inwersja;

  j=0     i=1 (tutaj wartość i > wartość j) czyli ++inwersja;

           j=0    i=1 (wartość i < wartość j)

                  j=0   i=1 (wartość i > wartość j) czyli ++inwersja

W ten sposób wychodzi 3, a powinno być 2, więc źle rozumiem to zadanie, czy mógłby mnie ktoś nakierować ?

Łopatologicznie rzecz ujmując inwersja zachodzi wtedy, gdy element mniejszy występuje po elemencie większym, niezależnie od tego ile innych elementów je dzieli.
I tak w pierwszym przypadku pary (2 1) i (3 1) są inwersjami które liczymy (rzecz jasna mowa o drugiej jedynce).

Inwersje są dla (2, 1) i (3, 1) przy czym odnoszą się do drugiej jedynki. Reszta ma dobry porządek. Nie wiem skąd ci się wzięły 3 inwersje.

mógł by ktoś rzucić okiem, bo działać działa, ale miałem problem co wymyślić aby móc porównywać jakiś element ciągu np. 4 czyli tab[3] z wszystkimi poprzednimi, jak widać wepchnąłem tam while który to robi, ale to tak trochę na siłę bo np. zawsze tam wykonuje bezsensowne porównanie czy sam jest mniejszy od siebie (ten element - indeks "i"). Czy jest jakiś lepszy, szybszy sposób ?

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int n=0,sum=0,j=0,lt=0;
    cin>>lt;
    for(int g=0; g<lt; ++g){
    cin>>n;
    int tab[n];
    for(int c=0; c<n; ++c)
    {
            cin>>tab[c];
    }
    for(int i=1; i<n; ++i)
    {
            if(tab[i]<tab[j])
                             ++sum;
            while(j!=i)
            {
                       ++j;
                       if(tab[i]<tab[j])
                                        ++sum;
            }
            j=0;
    }
    cout<<sum;
    sum=0;
    }
    return 0;
}

Jest szybszy sposób, przez divide and conquer, bardzo podobnie do sortowania przez scalanie (poza scalaniem liczysz liczbę inwersji pomiędzy jedną posortowaną tablicą i drugą).

Jeśli dobrze zrozumiałem, to n-ty element będzie tworzył inwersję jeśli jakikolwiek element przed nim jest od niego większy tak? W takim razie wystarczy przeszukać liniowo dane wejściowe, zapamiętywać wartość maksymalną z dotychczas odwiedzonych i jeśli aktualnie odwiedzany element jest mniejszy od zapamiętanego maksimum to mamy inwersję.

1. W pętli dla wszystkich kolejnych danych powtarzaj

2.  jeśli *dana* jest mniejsza od *maksimum* to zwiększ licznik inwersji
   

3.  w przeciwnym razie przypisz do *maksimum* wartość *danej*</del>
   

Aj, źle zrozumiałem. Przecież n-ty element może mieć kilka inwersji.

Rozwiązanie dla ciągów składających się z liter, a nie liczb: http://4programmers.net/Forum/Algorytmy/188575-oi_-_rozwiazania?p=791110#id791110
W wątku są również inne rozwiązania.