Given a list of integers, return the nth smallest integer in the list. **Only distinct elements should be considered** when calculating the answer. `n` will always be positive (`n > 0`)
If the nth small integer doesn't exist, return `-1` (C++) / `None` (Python) / `nil` (Ruby) / `null` (JavaScript).
Notes:
* "indexing" starts from 1
* huge lists (of 1 million elements) will be tested
## Examples
```python
nth_smallest([1, 3, 4, 5], 7)        ==> None  # n is more than the size of the list
nth_smallest([4, 3, 4, 5], 4)        ==> None  # 4th smallest integer doesn't exist
nth_smallest([45, -10, 4, 5, 4], 4)  ==> 45    # 4th smallest integer is 45
```
If you get a timeout, just try to resubmit your solution. However, if you ***always*** get a timeout, review your code.
import random

def partition(vector, left, right, pivotIndex):
    pivotValue = vector[pivotIndex]
    vector[pivotIndex], vector[right] = vector[right], vector[pivotIndex]  # Move pivot to end
    storeIndex = left
    for i in range(left, right):
        if vector[i] < pivotValue:
            vector[storeIndex], vector[i] = vector[i], vector[storeIndex]
            storeIndex += 1
    vector[right], vector[storeIndex] = vector[storeIndex], vector[right]  # Move pivot to its final place
    return storeIndex

def select(vector, left, right, k):
    "Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive."
    if k < len(vector):
        while True:
            pivotIndex = random.randint(left, right)     # select pivotIndex between left and right
            pivotNewIndex = partition(vector, left, right, pivotIndex)
            pivotDist = pivotNewIndex - left
            if pivotDist == k:
                return vector[pivotNewIndex]
            elif k < pivotDist:
                right = pivotNewIndex - 1
            else:
                k -= pivotDist + 1
                left = pivotNewIndex + 1

def nth_smallest(arr, n):
    unique = list(set(arr))
    return select(unique, 0, len(unique)-1, n-1)
import random

def partition(vector, left, right, pivotIndex):
    pivotValue = vector[pivotIndex]
    vector[pivotIndex], vector[right] = vector[right], vector[pivotIndex]  # Move pivot to end
    storeIndex = left
    for i in range(left, right):
        if vector[i] < pivotValue:
            vector[storeIndex], vector[i] = vector[i], vector[storeIndex]
            storeIndex += 1
    vector[right], vector[storeIndex] = vector[storeIndex], vector[right]  # Move pivot to its final place
    return storeIndex

def select(vector, left, right, k):
    "Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive."
    if k < len(vector):
        while True:
            pivotIndex = random.randint(left, right)     # select pivotIndex between left and right
            pivotNewIndex = partition(vector, left, right, pivotIndex)
            pivotDist = pivotNewIndex - left
            if pivotDist == k:
                return vector[pivotNewIndex]
            elif k < pivotDist:
                right = pivotNewIndex - 1
            else:
                k -= pivotDist + 1
                left = pivotNewIndex + 1

def nth_smallest(arr, n):
    unique = list(set(arr))
    return select(unique, 0, len(unique)-1, n-1)