A logistics company manages a warehouse inventory represented by an array of n positive integers a[1..n]. Each a[i] is the number of items in shelf i, arranged in a row of shelves.
Due to space optimization rules, the inventory on the shelves must be non-decreasing from left to right (i.e., a[1] ≤ a[2] ≤ ... ≤ a[n]).
The company can perform the following operation any number of times on any shelf:
Reduce the number of items on a shelf to any divisor of the current number of items.
Your task is to determine the minimum number of adjustments (operations) required to make the inventory non-decreasing.
Constraints
1 ≤ n ≤ 2⋅10^5
1 ≤ a[i] ≤ 10^9
Input Format
The first line contains an integer n — the number of shelves.
The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9) — the current number of items on each shelf.
Output Format
Print a single integer — the minimum number of operations needed to make the inventory non-decreasing.
Example 1
Input:
5
10 6 8 12 15
Output:
1
Explanation:
One way to adjust the shelves:
Reduce shelf 1 from 10 → 5 (operation 1).
Shelf 2 is 6, shelf 3 8 is already ≥ 6, so no operation
The final inventory [5,6,8,12,15] is non-decreasing. Total operations = 1
Log In to solve the Question