#include "bubblesort2.h"
#include <set>
#include <algorithm>
//#include <iostream>
using namespace std;
class Number{
public:
int Val;
int OriginalPos;
Number(){}
Number(const int& Val_, const int& OriginalPos_): Val(Val_), OriginalPos(OriginalPos_){}
bool operator<(const Number& obj)const{
if(this->Val != obj.Val) return (this->Val < obj.Val);
else return (this->OriginalPos < obj.OriginalPos);
}
};
int solve(const set<Number>& NumberSet, vector<int>& dif){
const int& N = dif.size();
int min_ = 0;
set<Number>::iterator it = NumberSet.begin();
for(int i = 0; i < N; ++i, ++it){
min_ = min(min_, i - it->OriginalPos);
if(i - (N-1) > min_) break;
}
return -min_;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
/*
4 2
1 2 3 4
0 3
2 1
=>1
=>2
*/
const int& N = A.size();
const int& Q = X.size();
vector<Number> NumberVtr(N);
for(int i = 0; i < N; ++i)
NumberVtr[i] = Number(A[i], i);
set<Number> NumberSet(NumberVtr.begin(), NumberVtr.end());
vector<int> answer(Q);
vector<int> dif(N);
for(int i = 0; i < Q; ++i){
const int& index_NumberToChange = X[i];
Number& NumberToChange = NumberVtr[index_NumberToChange];
NumberSet.erase(NumberSet.find(NumberToChange));
NumberToChange.Val = V[i];
NumberSet.insert(NumberToChange);
answer[i] = solve(NumberSet, dif);
}
// cout << "answer: ";
// for(int i = 0; i < Q; ++i)
// cout << answer[i] << " ";
// cout << endl;
return answer;
}
