#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, X;
ll A[200005], L[200005], R[200005];
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> X;
for(int i = 0; i < N; i++){
cin >> A[i];
}
vector<ll> dp;
for(int i = 0; i < N; i++){
if(dp.empty() || dp.back() < A[i]) dp.push_back(A[i]);
else *lower_bound(dp.begin(), dp.end(), A[i]) = A[i];
L[i] = dp.size();
}
dp.clear();
for(int i = N - 1; i >= 0; i--){
if(dp.empty() || dp.back() < A[i]) dp.push_back(A[i]);
else *lower_bound(dp.begin(), dp.end(), A[i]) = A[i];
R[i] = dp.size();
}
ll ans = 0;
for(int i = 0; i < N; i++) ans = max(ans, L[i] + R[i] - 1);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
42 ms |
4960 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
1492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
2620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |