SPOJ:SMCNT

Hi /prog/,
I'm trying to solve a challenge a friend gave me.
I have a huge list A[] (10^6 in length) of numbers, and for each k i have to print the number of A[k'] with: k' > k and A[k'] < A[k].
Example:
In: 12 5 7 3 0 1
Out: 5 3 3 2 0 0

I've thought about using a research binary tree or a red-black tree. Thoughts ?
(excuse my English, it's not my natural tongue.)

excuse my English, it's not my natural tongue.

Jew detected!

>>1
Primero, you aren't gonna get any help here. This joint is dominated by minimum wage monkeys who google shit and computer science majors who don't actually read nor code.

>>3
Do you recommend somewhere in particular ?

>>3
DOMINATE MY ANUS

>>2
What the fuck is wrong with you.

>>6
Hes an OCD shitcunt spammer that probably had his dick mutulated.

I don't know how far a simplistic naïve approach would get you, but why not try something like...

nums = gets(nil).split.map { |x| x.to_i }
counts = Array.new(nums.size, 0)

nums.each_with_index do |n, i|
  i.times do |j|
    counts[j] += 1 if n < nums[j]
  end
end

puts counts.join(' ')

>>8
Yeah, I already thought about it, but I have 10^6 numbers. Your solution is in O(n²).
Using an research binary tree, it should be more like O(n.logn), which is way better.