#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <list>
#include <iostream>
#include <string>
#include <map>
using namespace std;
int binarySearch(int* searchSpace, int s, int e, int num)
{
int ans;
while (s <= e)
{
int mid = (s + e) / 2;
if (searchSpace[mid] >= num)
{
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}
int longestSubArr(int* arr, int n)
{
int searchSpace[n];
int index[n];
int j = 0;
int ans = 0;
for (int i = 0; i < n; ++i)
{
if (j == 0 or searchSpace[j - 1] < arr[i])
{
searchSpace[j] = arr[i];
index[j] = i;
j++;
}
int idx = binarySearch(searchSpace, 0, j - 1, arr[i]);
ans = max(ans, i - index[idx] + 1);
}
return ans;
}
int main(int argc, char const* argv[])
{
int t;
scanf("%d", &t);
int array[t];
for (int i = 0; i < t; ++i)
{
scanf("%d", &array[i]);
}
int n = sizeof(array) / sizeof(array[0]);
cout << longestSubArr(array, n)-1 << endl;
return 0;
}
Copy