#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
int lds (vector<int> a) {
vector<int> vec;
reverse(a.begin(), a.end());
for (int i : a) {
if (vec.empty()) vec.push_back(i);
else if (vec.back() < i) vec.push_back(i);
else {
vec[lower_bound(vec.begin(), vec.end(), i) - vec.begin()] = i;
}
}
return vec.size();
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q = X.size();
std::vector<int> answer(Q);
for (int i = 0; i < Q; i++) {
A[X[i]] = V[i];
answer[i] = lds(A);
}
return answer;
}
