A UNIQUE APPROACH | | BEATS 100% | |  LINKED LIST | | DETAILED EXPLANATION 
🔹 IntuitionTo make the array non-decreasing, we are allowed to merge any two adjacent elements into their sum and remove the second one. However, to minimize th
### 🔹 Intuition

To make the array non-decreasing, we are allowed to **merge any two adjacent elements** into their sum and remove the second one. However, to minimize the number of such operations, we need a strategy that makes the array non-decreasing in as few steps as possible.

A key idea is that **removing the "most problematic" adjacent pairs early**—those that cause a decrease—is helpful. Among all such adjacent pairs, merging the one with the **smallest sum** is the safest bet since it introduces a relatively small new number into the array and is less likely to create new decreases.

---

### 🔹 Approach

1. Convert the input vector to a `list<int>` for efficient element removal and splicing (as `list` supports O(1) deletion and insertion).
2. Repeatedly check if the current sequence is non-decreasing. If yes, we’re done.
3. If not, find the pair of adjacent elements with the **smallest sum**.
4. Merge them: update the first element with the sum and erase the second element.
5. Increment the operation count and repeat the process.

The process terminates when the list becomes non-decreasing.

---

### 🔹 Time and Space Complexity

- **Time Complexity:**  
  Worst-case is `O(n²)`, because:
  - In each operation, we may scan the entire list to find the smallest pair → `O(n)`
  - We might perform up to `O(n)` such operations in the worst case  
  Hence, total worst-case time is `O(n²)`.

- **Space Complexity:**  
  `O(n)` for storing the list version of the input array.

---

### 🔹 Code

```cpp
class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        list<int> lst(nums.begin(), nums.end());
        int ops = 0;

        while (true) {
            // Check if the list is non-decreasing
            bool nonDecreasing = true;
            for (auto it = next(lst.begin()); it != lst.end(); ++it) {
                if (*it < *prev(it)) {
                    nonDecreasing = false;
                    break;
                }
            }
            if (nonDecreasing) break;

            // Find the pair with the minimum sum
            auto minIt = lst.begin();
            auto nextIt = next(minIt);
            int minSum = *minIt + *nextIt;

            for (auto it = lst.begin(); next(it) != lst.end(); ++it) {
                int sum = *it + *next(it);
                if (sum < minSum) {
                    minIt = it;
                    nextIt = next(it);
                    minSum = sum;
                }
            }

            // Merge the pair
            *minIt = *minIt + *nextIt;
            lst.erase(nextIt);
            ops++;
        }

        return ops;
    }
};
```
['C++']