<p>You are given an integer array <code>nums</code> of length <code>n</code> which represents a permutation of all the integers in the range <code>[0, n - 1]</code>.</p>

<p>The number of <strong>global inversions</strong> is the number of the different pairs <code>(i, j)</code> where:</p>

<ul>
	<li><code>0 &lt;= i &lt; j &lt; n</code></li>
	<li><code>nums[i] &gt; nums[j]</code></li>
</ul>

<p>The number of <strong>local inversions</strong> is the number of indices <code>i</code> where:</p>

<ul>
	<li><code>0 &lt;= i &lt; n - 1</code></li>
	<li><code>nums[i] &gt; nums[i + 1]</code></li>
</ul>

<p>Return <code>true</code> <em>if the number of <strong>global inversions</strong> is equal to the number of <strong>local inversions</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> There is 1 global inversion and 1 local inversion.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,0]
<strong>Output:</strong> false
<strong>Explanation:</strong> There are 2 global inversions and 1 local inversion.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt; n</code></li>
	<li>All the integers of <code>nums</code> are <strong>unique</strong>.</li>
	<li><code>nums</code> is a permutation of all the numbers in the range <code>[0, n - 1]</code>.</li>
</ul>

class Solution {
public:
   long long ct=0;
void merge(vector<int>& arr,int s,int e){
   if(s>=e){
    return;
   }
    int mid=(s+e)/2;
    int l1=mid-s+1;
    int l2=e-mid;
    //creating two arrays
    int* left=new int[l1];
    int* right=new int[l2];

     //copy values
     int k=s;
     for (int i = 0; i <l1; i++)
     {
        left[i]=arr[k];
        k++;
     }
     k=mid+1;
     for (int i = 0; i < l2; i++)
     {
        right[i]=arr[k];
        k++;
     }
     //merge logic
     int i=0;
     int j=0;
    int m=s;
     while (i<l1&&j<l2)
     {
        if (right[j]<left[i])
        {
            arr[m++]=right[j++];
            ct+=(l1-i);
        }else{
            arr[m++]=left[i++];
            
        }
        
     }
     if (i<l1)
     {
        arr[m++]=left[i++];
     }
     if (j<l2)
     {
        arr[m++]=right[j++];
     }

    
}
void mergesort(vector<int>& arr,int s,int e){
    if (s>=e)
    {
      return;
    }
    
    long long mid=(s+e)/2;
    
    //sort left wala part
    mergesort(arr,s,mid);
    //sort right wala part
    mergesort(arr,mid+1,e);
    //merging two parts
    merge(arr,s,e);
}
    bool isIdealPermutation(vector<int>& nums) {
        int c=0;
        int n=nums.size();
        for(int i=0;i<n-1;i++){
            if(nums[i]>nums[i+1]){
                c++;
            }
        }
        mergesort(nums,0,n-1);
        if(c==ct){
            return true;
        }
        return false;
        
    }
};
155990