right greater-thans

Write a function accepting a list of integers l and returning a list of integer c such that the ith element of c equals the number of elements in l that are to the right of the ith element of l and greater than that element (that is, c[i] = #(l[i] < l[j] : i < j < |l|).

``` \$ cat rgc.rkt
#lang racket

(define (rgc-l l)

; Given the integer list l, return an integer list c where
; c[i] equals the number of elements in l(i..|l|) that are
; greater than l[i].

(let loop ((l l) (c '()))

(if (null? l)

(reverse c)

(let*

((e (car l))
(l (cdr l))
(cnt (foldr (lambda (e2 c) (if (< e e2) (+ c 1) c))
0 l)))

(loop l (cons cnt c))))))

(define (rgc-v l)

; Given the integer list l, return an integer list c where
; c[i] equals the number of elements in l(i..|l|) that are
; greater than l[i].

(if (null? l)
'()
(let*

((v (list->vector l))
(n (length l))
(cnts (make-vector n)))

(vector->list
(do ((i (- n 1) (- i 1))) ((< i 0) cnts)

(let*

((e (vector-ref v i))
(c 0)
(cnt (do ((j (+ i 1) (+ j 1))) ((= j n) c)
(when (< e (vector-ref v j))
(set! c (+ c 1))))))

(vector-set! cnts i cnt)))))))

(module+ test

(require rackunit "utl.rkt")

(define (run-test f)
(check-equal? (f '()) '())
(check-equal? (f '(1)) '(0))
(check-equal? (f '(1 2)) '(1 0))
(check-equal?
(f '(10 12 8 17 3 24 19)) '(4 3 3 2 2 0 0)))

(run-test rgc-v)
(run-test rgc-l)

(do ((i 0 (+ i 1))) ((= i 100) (void))
(let ((l (random-list (random 100))))
(check-equal? (rgc-v l) (rgc-l l))))

(define (time-it f n iters seed)

(random-seed seed)

(let loop ((t 0) (i 0))
(if (= i iters)
(inexact->exact (round (/ t iters)))
(let ((l (random-list n)))
(let-values
(((a b c d) (time-apply f (list l))))
(loop (+ t b) (+ i 1)))))))

(let ((iters 10))
(do ((i 1000 (+ 1000 i))) ((> i 10000) (void))
(printf "n: ~a, rgc-l: ~a, rgc-v: ~a\n"
i
(time-it rgc-l i iters i)
(time-it rgc-v i iters i))))
)

\$ raco test rgc.rkt
raco test: (submod "rgc.rkt" test)
n: 1000, rgc-l: 19, rgc-v: 8
n: 2000, rgc-l: 75, rgc-v: 30
n: 3000, rgc-l: 171, rgc-v: 66
n: 4000, rgc-l: 314, rgc-v: 118
n: 5000, rgc-l: 549, rgc-v: 184
n: 6000, rgc-l: 878, rgc-v: 269
n: 7000, rgc-l: 1339, rgc-v: 368
n: 8000, rgc-l: 1862, rgc-v: 478
n: 9000, rgc-l: 2430, rgc-v: 604
n: 10000, rgc-l: 3077, rgc-v: 733
108 tests passed

\$
```