#lang racket/base

;;; This benchmark is a adapted from the version from Grift
;;; Original source://github.com/Gradual-Typing/benchmarks
;;; Since there was no racket version of this benchmark we adapted
;;; the Grift version.

;; Modified from the original version to remove special symbols from
;; identifiers in order to avoid errors when running the dynamizer

(define (mpair<= p1 p2)
  (let ([p1-fst (vector-ref p1 0)]
        [p2-fst (vector-ref p2 0)])
    (cond
      [(< p1-fst p2-fst)
       #t]
      [(= p1-fst p2-fst)
       (<= (vector-ref p1 1) (vector-ref p2 1))]
      [else #f])))

(define (partition a p r)
  (let ([i (box (- p 1))]
        [x (vector-ref a r)])
    (for ([j (in-range p r)])
      (if (mpair<= (vector-ref a j) x)
          (begin
            (set-box! i (+ (unbox i) 1))
            (swap a (unbox i) j))
          (void))) 
    (swap a (+ (unbox i) 1) r)
    (+ (unbox i) 1)))

(define (swap a i j)
  (if (= i j)
      (void)
      (let ([t (vector-ref a i)])
        (begin
          (vector-set! a i (vector-ref a j))
          (vector-set! a j t)))))

(define (sort a p r)
  (if (< p r)
    (let ([q (partition a p r)])
      (begin
        (sort a p (- q 1))
        (sort a (+ q 1) r)))
    (void)))

(define (main)
  (let ([size (read)])
    (let ([pair (make-vector 2)])
      (vector-set! pair 0 (read))
      (vector-set! pair 1 (read))
      (let ([a (make-vector size)])
        (vector-set! a 0 pair)
        (for ([i (in-range 1 size)])
          (let ([pair (make-vector 2)])
            (vector-set! pair 0 (read))
            (vector-set! pair 1 (read))
            (vector-set! a i pair)))
        (sort a 0 (- size 1))
        (display (vector-ref (vector-ref a 0) 1))
        (newline)))))

(time (main))
