Let's see your ideas

You are given an array of integers. You have to find the shortest substring that contains only the elements from the interval [ A, B ]. Also, every integer from the interval [ A, B ] has to appear at least once in the substring. If there is no such substring output -1.


INPUT:
The first line contains three integers n, A and B (1 <= n <= 1.000.000, 1 <= A <= B <= 1.000.000.000). The following line contains n integers from the interval [1, 1.000.000.000] representing the array.

OUTPUT:
Output the length of such shortest substring, or -1 if there is none.

Input:
22 5 7
5 7 8 6 1 1000 6 7 7 7 5 5 5 5 7 7 7 7 7 6 6 6

Output:
5

Explanation:
The shortest substring exists, its length is 5. It starts from the 7th element of the array.

EXPERT LINEAR SOLUTION

(define (shortest-substring-length a b z)
  (let* ((n (vector-length z))
         (d (- b a -1))
         (v (make-vector d 0)))
    (let loop ((s 0) (i 0) (t 0) (m (+ n 1)))
      (cond
        ((= t d)
         (let* ((c (- (vector-ref z s) a))
                (o (- (vector-ref v c) 1)))
           (vector-set! v c o)
           (loop (+ s 1) i (if (zero? o) (- t 1) t) (min (- i s) m))))
        ((= i n)
         (if (= m (+ n 1)) -1 m))
        (else
         (let ((q (vector-ref z i)))
           (if (<= a q b)
               (let* ((c (- q a))
                      (o (vector-ref v c)))
                 (vector-set! v c (+ o 1))
                 (loop s (+ i 1) (if (zero? o) (+ t 1) t) m))
               (begin
                 (vector-fill! v 0)
                 (loop (+ i 1) (+ i 1) 0 m)))))))))

(let* ((n (read))
       (a (read))
       (b (read))
       (z (make-vector n)))
  (do ((i 0 (+ i 1)))
    ((= i n) (display (shortest-substring-length a b z)) (newline))
    (vector-set! z i (read))))

(define (test)
  (define ssl shortest-substring-length)
  (and
   (= 5 (ssl 5 7 '#(5 7 8 6 1 1000 6 7 7 7 5 5 5 5 7 7 7 7 7 6 6 6)))
   (= -1 (ssl 1 10 '#(1 2 3 4 6 7 8 9 10 9 8 7 6 4 3 2 1)))
   (= 1 (ssl 1 1 '#(0 1 2)))
   (= 3 (ssl 1 3 '#(1 2 2 3 4 1 1 2 3)))))