Given a list of integers, find the **n**-th smallest number, i.e., the number that appears at index **n** (0-based) when they are sorted in non-descending order. The numbers will be given in intervals. For example, the intervals (1, 3) and (5, 7) represent the list of numbers { 1, 2, 3, 5, 6, 7 }. A number may be present in more than one interval, and it appears in the list once for each interval it is in. For example, the intervals (1, 4) and (3, 5) represent the list of numbers { 1, 2, 3, 3, 4, 4, 5 }.
The intervals will be given as two int[]s, **lowerBound** and **upperBound**. The i-th elements of these int[]s represent the smallest and largest numbers in the i-th interval, inclusive. |