You are given an integer array arr.

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

&nbsp;
Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.


Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 2000
	0 &lt;= arr[i] &lt;= 108


class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        sortedArr = sorted(arr)

        posMap = defaultdict(list)
        for i in range(len(sortedArr)):
            posMap[sortedArr[i]].append(i) # keep track the right sortedArr[i] position

        idx = len(arr) - 1
        cnt = 0
        for i in range(len(arr) - 1, -1, -1):
            idx = min(idx, posMap[arr[i]][-1]) # the smallest position need to move arr[i] to correct position
            posMap[arr[i]].pop()
            if i == idx:
                cnt += 1
                idx -= 1
        return cnt
/*

1. Generate Right min
2. Generate Left Max
3. Count chunks

Pos -->. 0 1 2 3 4 5 6 7

Input --> 30 , 10 , 20 , 40 , 60 , 50 , 75 , 70
             <------------> <--> <-------> <------->
Left Max --> 30 , 30 , 30 , 40 , 60 , 60 , 75 , 75

Right Min --> 10 , 10 , 20 , 40 , 50 , 50 , 70 , 70 , Integer.max

1. At pos 2 , left_max 30 is smaller than right_min 40 at pos 3
2. That means , all the elements in the right side of 30 are bigger than all the elements of left side of 30 , including 30
3. Hence we can break it at pos 2 into a chunk and sort this whole sub-array( 0 - 2 )

*/

class Solution {

    public int maxChunksToSorted(int[] arr) {

        // 1. Generate Right min

        int[] min_from_right = new int[arr.length+1] ;
        min_from_right[arr.length] = Integer.MAX_VALUE ;

        for(int i=arr.length-1 ; i>=0 ; i--){
            min_from_right[i] = Math.min(arr[i] , min_from_right[i+1]);
        }

        // 2. Generate Left Max and Count chunks
        int chunk_count = 0 ;
        int max_cur = Integer.MIN_VALUE ;

        for(int i=0 ; i<arr.length ; i++){
            max_cur = Math.max(max_cur , arr[i]);
            if(max_cur <= min_from_right[i+1]){
                chunk_count++ ;
            }
        }

        return chunk_count ;
    }
}
class BIT {
 public:
  BIT(int capacity) : nodes(capacity + 1, 0) {}
  BIT(const vector<int>& nums) : nodes(nums.size() + 1, 0) {
    for (int i = 0; i < nums.size(); ++i) {
      update(i + 1, nums[i]);
    }
  }

  void update(int idx, int val) {
    for (int i = idx; i < nodes.size(); i += i & -i) {
      nodes[i] += val;
    }
  }

  int query(int idx) {
    int ans = 0;
    for (int i = idx; i > 0; i -= i & -i) {
      ans += nodes[i];
    }
    return ans;
  }

 private:
  vector<int> nodes;
};

class Solution {
 public:
  int maxChunksToSorted(vector<int>& arr) {
    int n = arr.size();
    BIT bit(n);
    unordered_map<int, int> h;
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    for (int i = 0; i < n; ++i) {
      if (i == 0 || sorted[i - 1] != sorted[i]) h[sorted[i]] = i + 1;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
      bit.update(h[arr[i]], 1);
      ++h[arr[i]];
      if (bit.query(i + 1) == i + 1) ans += 1;
    }
    return ans;
  }
};
var maxChunksToSorted = function(arr) {
    var rmin = new Array(arr.length).fill(0);
    rmin[arr.length] = Number.MAX_SAFE_INTEGER;
    
    for(var i=arr.length-1; i>=0; i--) {
        rmin[i] = Math.min(arr[i], rmin[i+1]);
    }
    
    var lmax = Number.MIN_SAFE_INTEGER;
    var count = 0;
    
    for(var i=0; i<arr.length; i++) {
        lmax = Math.max(arr[i], lmax);
        
        if(lmax <= rmin[i+1]) {
            count++;
        }
    }
    
    return count;
};``
Max Chunks To Make Sorted II