library Arrays {
    /**
     * @dev Searches a sorted `array` and returns the first index that contains
     * a value greater or equal to `element`. If no such index exists (i.e. all
     * values in the array are strictly less than `element`), the array length is
     * returned. Time complexity O(log n).
     *
     * `array` is expected to be sorted in ascending order, and to contain no
     * repeated elements.
     */
    function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
        if (array.length == 0) {
            return 0;
        }

        uint256 low = 0;
        uint256 high = array.length;

        while (low < high) {
            uint256 mid = Math.average(low, high);

            // Note that mid will always be strictly less than high (i.e. it will be a valid array index)
            // because Math.average rounds down (it does integer division with truncation).
            if (array[mid] > element) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        // At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
        if (low > 0 && array[low - 1] == element) {
            return low - 1;
        } else {
            return low;
        }
    }
}
/**
 * @dev Collection of functions related to array types.
 */
function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
    if (array.length == 0) {
        return 0;
    }

    uint256 low = 0;
    uint256 high = array.length;

    while (low < high) {
        uint256 mid = Math.average(low, high);

        // Note that mid will always be strictly less than high (i.e. it will be a valid array index)
        // because Math.average rounds down (it does integer division with truncation).
        if (array[mid] > element) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    // At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
    if (low > 0 && array[low - 1] == element) {
        return low - 1;
    } else {
        return low;
    }
}

/**
 * @dev Searches a sorted `array` and returns the first index that contains
 * a value greater or equal to `element`. If no such index exists (i.e. all
 * values in the array are strictly less than `element`), the array length is
 * returned. Time complexity O(log n).
 *
 * `array` is expected to be sorted in ascending order, and to contain no
 * repeated elements.
 */