I was trying to solve this question Problem using the concept that answer would be the longest non increasing sequence but it fails on some test cases idk why? Please help me sort it out. Here is my Soln: ~~~~~

#include <bits/stdc++.h>
using namespace std;

int find_lis(vector<int> a) {
    vector<int> dp;
    for (int i : a) {
        int pos = upper_bound(dp.begin(), dp.end(), i)- ``dp.begin();
        if (pos == dp.size()) {
            // we can have a new, longer increasing subsequence!
            dp.push_back(i);
        } else {
            // oh ok, at least we can make the ending element smaller
            dp[pos] = i;
        }
    }
    return dp.size();
}
int main(){
    ifstream fin("cowjog.in");
    ofstream fout("cowjog.out");
    int  n,t;fin>>n>>t;
    vector<vector<int>> v(n, vector<int>(2));
    for(int i=0;i<n;i++) { int x,y;fin>>x>>y; v[i][0]=x, v[i][1]=y; }

    sort(v.begin(), v.end());
    
    vector<int> vec(n);
    for(int i=0;i<n;i++){
        vec[i]=(v[i][0]+t*v[i][1]);
    }
    reverse(vec.begin(), vec.end());
    fout<<find_lis(vec)<<endl;
}

~~~~~

I was asked this question in the interview round of a company: Given an array of integers of size atleast 3, such that a[0]>=a[1].... And a[n-2]<=a[n-1] such that it gives a v shape (i.e. first it’s decreasing then its increasing) find the minimum element in the array.

The interviewer asked to implement in O(log n) , if all the elements would have been distinct then I coded the approach using binary search but could not come up with a log n solution in case of duplicates. I was asked to code it using recursion also. Can someone help me out?

Can someone tell the approach for this interesting question: Question