You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:


	You choose any number of obstacles between 0 and i inclusive.
	You must include the ith obstacle in the course.
	You must put the chosen obstacles in the same order as they appear in obstacles.
	Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.


Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.

&nbsp;
Example 1:

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.


Example 2:

Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.


Example 3:

Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.


&nbsp;
Constraints:


	n == obstacles.length
	1 &lt;= n &lt;= 105
	1 &lt;= obstacles[i] &lt;= 107


from bisect import bisect_right
class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        longest, res = [], []
        for i in range(len(obstacles)):
            idx = bisect_right(longest, obstacles[i])
            if idx == len(longest):
                longest.append(obstacles[i])
            else:
                longest[idx] = obstacles[i]
            res.append(idx+1)
        return res
class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int i = -1, cur = 0, lisSize = -1;
        int[] lis = new int[obstacles.length];
        int[] ans = new int[obstacles.length];
        
        for (int curHeight: obstacles) {
            if (i == -1 || lis[i] <= curHeight) {
                lis[++i] = curHeight;
                lisSize = i;
            } else {
                lisSize = search(lis, 0, i, curHeight);
                lis[lisSize] = curHeight;
            }
            
            ans[cur++] = lisSize + 1;
        }
        
        return ans;      
    }
    
    private int search(int[] nums, int start, int end, int target) {
        int left = start, right = end;
        int boundary = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                boundary = mid;
                right = mid - 1;
            } else left = mid + 1;
        }
        return boundary;
    }
}
class Solution {
public:
	// ranking each element to make segment tree of small size
    void compress(vector<int>& a){
        vector<int> b=a;
        sort(b.begin(),b.end());
        map<int,int> mp;
        int prev=b[0],rnk=0,n=a.size();
        for(int i=0;i<n;i++){
            if(b[i]!=prev){
                prev=b[i];
                rnk++;
            }
            mp[b[i]]=rnk;
        }
        for(int i=0;i<n;i++)
            a[i]=mp[a[i]];
    }
    
    void update(int st[],int tind,int ind,int val,int tl,int tr){
        if(tl>tr)
            return;
        if(tl==tr){
            st[tind]=val;
            return;
        }
        int m=tl+(tr-tl)/2,left=tind<<1;
        if(ind<=m)
            update(st,left,ind,val,tl,m);
        else
            update(st,left+1,ind,val,m+1,tr);
        st[tind]=max(st[left],st[left+1]);
    }
    
    int query(int st[],int tind,int tl,int tr,int ql,int qr){
        if(tl>tr or ql>tr or qr<tl)
            return 0;
        if(ql<=tl and tr<=qr)
            return st[tind];
        int m=tl+(tr-tl)/2,left=tind<<1;
        return max(query(st,left,tl,m,ql,qr),query(st,left+1,m+1,tr,ql,qr));
    }

    vector<int> longestObstacleCourseAtEachPosition(vector<int>& a) {
        compress(a);
        int i,n=a.size();
        int st[4*n+10];
        memset(st,0,sizeof(st));
        update(st,1,a[0],1,0,n-1);
        vector<int> dp(n);
        dp[0]=1;
        
        for(i=1;i<n;i++){
            int mx=query(st,1,0,n-1,0,a[i]);
            dp[i]=1+mx;
            update(st,1,a[i],dp[i],0,n-1);
        }
        
        return dp;
    }
};
var longestObstacleCourseAtEachPosition = function(obstacles) {
    var n = obstacles.length;
    var lis = [];
    var res = new Array(n).fill(0);
    for(var i = 0; i<n; i++)
    {
        if(lis.length>0 && obstacles[i] >= lis[lis.length-1])
        {
            lis.push(obstacles[i]);
            res[i] = lis.length;
        }
        else
        {
            // find the upper bound
            var l = 0;
            var r = lis.length;
            while(l<=r)
            {
                var mid = Math.floor((l+r)/2);
                if(lis[mid]<=obstacles[i])
                {
                    l = mid+1;
                }
                else
                {
                    r = mid-1;
                }
            }
            lis[l] = obstacles[i];
            res[i] = l+1;
        }
    }
    return res;
}
Find the Longest Valid Obstacle Course at Each Position