Maybe you should sometimes run your programs on your own computer before submitting them. The you would've probably noticed that you output an 'n' instead of a 'n'.

Btw, I just realized that one does not actually has to sort the sequence. Simply determining the "degree of unsortedness" is enough. I'll leave it to you to find out what I mean with that

Please define "inversions". But I guess you mean the right thing. Linear time possible? Hmm, maybe. I'll have to think about it. Intuitively, I would say yes.

I think I mean it like A > A[j] and i < j. Not very good with this kind of mathematical notations. But actually I don't really need a linear time, just anything that's better than quadratic...

junjieliang: So you "need" something that's better than quadratic? Unfortunately, the input cases are so small, that quadratic solutions go through in zero time. What do you need it for? A homework assignment?

I tried to get it down to linear time today, but didn't succeed. Nothing really worked. But I'm not yet ready to give it up.

Fine, I do have a motive. It's for solving another problem, where quadratic would be too slow (but that's over at timus). Since this was brought up I decided to ask around...

begin
Readln(t);
for tt:=1 to t do begin
Readln(l);
for i:=1 to l do
if i<>l then
Read(Train)
else
Readln(Train);
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]

begin
Readln(t);
for tt:=1 to t do begin
Readln(l);
for i:=1 to l do
if i<>l then
Read(Train)
else
Readln(Train);
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]