Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the sequence (a[i],b[i]) such that if $$b[i]='<'$$ then $$a[i+1]<a[i]$$ and if $$b[i]='>'$$ then $$a[i+1]>a[i]$$.

My idea: I tought about constructing the array dp[] such that dp[i] represents the maximum length of the longest sequence of (a[i],b[i]) with the given properties. I constructed it from the end like this:

$$b[i]='>'$$ then
$$dp[i] = max(1+dp[j], i < j <= n \&\& nr[j] > nr[i])$$
and if $$b[i]='<'$$ then $$dp[i] = max(1+dp[j], i < j <= n \&\& nr[j] < nr[i])$$
The difficulty of the problem lies in finding the number $max(1+dp[j], i < j <= n \&\& nr[j] < nr[i])$ and $max(1+dp[j], i < j <= n \&\& nr[j] > nr[i])$
I implemented this by using a search tree which with all the elements of dp[] from $n$ to $i+1$ and then do the corresponding query depending on the sign. However, this solution turned up not to be very efficient since it takes more than 0.15 seconds for certain tests. 

May somebody help solve this with a more efficient algorithm.

This is what I tried:


    #include <iostream>
    
    using namespace std;
    int tree[400001],dp[101001],h[400001];
    struct af
    {
        int nr;
        char rs;
    }v[101001];
    int op(int x,int y)
    {
        return x<y?y:x;
    }
    void update(int node, int left, int right, int pos, int val) {
        if (left == right) {
            tree[node] = val;
            h[node]=v[left].nr;
            return;
        }
        int mid = (left + right) / 2;
        if (pos <= mid)
            update(2 * node, left, mid, pos, val);
        else
            update(2 * node + 1, mid + 1, right, pos, val);
        tree[node] = op(tree[2 * node] , tree[2 * node + 1]);
    }
    int query(int node,int left,int right,int x,int y)
    {
        if(x<=left && right<=y)
            return dp[node];
        int mid=(left+right)/2;
        int ans1=0,ans2=0;
        if(x<=mid) ans1=query(2*node,left,mid,x,y);
        if(y>mid) ans2=query(2*node+1,mid+1,right,x,y);
        return op(ans1,ans2);
    
    }
    int query1(int node, int left, int right, int x, int y,int z) {
        if(x <= left && right <= y && left==right)
        {
            
            if(h[node]>z && (h[node]!=0))
            {
                
                return tree[node];
            }
            else return 0;
    
        }
        int mid = (left + right) / 2;
        int ans1 = 0, ans2 = 0;
    
        if(x <= mid)
           {ans1 = query1(2 * node, left, mid, x, y,z);}
        if(y > mid)
           ans2 = query1(2 * node + 1, mid + 1, right, x, y,z);
        return op(ans1 , ans2);
    }
    int query2(int node, int left, int right, int x, int y,int z) {
        if(x <= left && right <= y && left==right)
        {
            if(h[node]<z && (h[node]!=0))
            return tree[node];
            else return 0;
        }
        int mid = (left + right) / 2;
        int ans1 = 0, ans2 = 0;
        if(x <= mid)
           ans1 = query2(2 * node, left, mid, x, y,z);
        if(y > mid)
           ans2 = query2(2 * node + 1, mid + 1, right, x, y,z);
        return op(ans1 , ans2);
    }
    void build(int node, int left, int right){
        if(left == right){
           tree[node] = dp[left];
           h[node]=v[left].nr;
           return;
        }
        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
        tree[node] = op(tree[2 * node],tree[2 * node + 1]);
    }
    int n;
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;++i) cin>>v[i].nr>>v[i].rs;
        
        dp[n]=1;
        update(1,1,n,n,1);
        for(int i=n-1;i>0;--i)
        {
                
            if(v[i].rs=='>')
            {
                
                dp[i]=query1(1,1,n,i+1,n,v[i].nr);
                dp[i]++;
            }
            if(v[i].rs=='<')
            {
                dp[i]=query2(1,1,n,i+1,n,v[i].nr);
                dp[i]++;
            }
            update(1,1,n,i,dp[i]);
        }
        cout<<tree[1];
        return 0;
    }