You are given an array of non-overlapping intervals intervals sorted in ascending order by start time. Given a new interval newInterval = [start, end], insert it into the sorted intervals (merging if necessary).

Return the resulting intervals array. You do not need to modify the original intervals array.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5