def pair_partitions(L, R):
    """ Returns which partitions to pair for the merge_asof algorithm and the
    bounds on which to split them up
    """
    result = []
    n, m = len(L) - 1, len(R) - 1
    i, j = 0, -1
    while R[j + 1] <= L[i]:
        j += 1
    J = []
    while i < n:
        partition = 0 if j < 0 else m - 1 if j >= m else j
        lower = R[j] if j >= 0 and R[j] > L[i] else None
        upper = R[j + 1] if j + 1 < m and (i == n - 1 or R[j + 1] < L[i + 1]
            ) else None
        J.append((partition, lower, upper))
        i1 = i + 1 if j + 1 == m or i + 1 < n and R[j + 1] >= L[i + 1] else i
        j1 = j + 1 if i + 1 == n or j + 1 < m and L[i + 1] >= R[j + 1] else j
        if i1 > i:
            result.append(J)
            J = []
        i, j = i1, j1
    return result
