Get Minimum Operations to Sort Array

Problem

You are given an unsorted array containing n elements. In one operation, choose any element arr[i] and divide it into two positive integers a and b such that:

a + b = arr[i]
a > 0
b > 0

An element may be split any number of times. Determine the smallest number of operations needed to arrange the resulting array in ascending order.

Constraints

• 1 <= n <= 10^5
• 1 <= arr[i] <= 10^9

Example

Input:

arr = [3, 4, 3]
n = 3

Output:

2

This means that two split operations are sufficient to sort the array in ascending order.