#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
bool sorted(vector<int> a) {
int n = a.size();
for (int i=1; i<n; i++) {
if (a[i] < a[i-1]) return false;
}
return true;
}
int brute(vector<int> a) {
int n = a.size();
int res = 0;
while (!sorted(a)) {
res++;
for (int i=0; i<n-1; i++) {
if (a[i] > a[i+1]) swap(a[i], a[i+1]);
}
}
return res;
}
int solve(vector<int> a) {
vector<int> sa = a;
int n = a.size();
sort(sa.begin(), sa.end());
map<int,vector<int>> inds;
for (int i=n-1; i>=0; i--) {
inds[sa[i]].push_back(i);
}
int mx = 0;
for (int i=0; i<n; i++) {
int to = inds[a[i]].back();
if (to < i) {
mx = max(mx, i-to);
}
inds[a[i]].pop_back();
}
return mx;
}
void print(vector<int> a) {
for (int i: a) cout<<i<<" ";
cout<<endl;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int Q = X.size();
vector<int> res(Q);
for (int i=0; i<Q; i++) {
A[X[i]] = V[i];
//print(A);
//cout<<solve(A)<<" ans: "<<brute(A)<<endl;
//assert(brute(A) == solve(A));
res[i] = solve(A);
}
return res;
}
/*
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//out(brute({7, 4, 6, 3, 1, 3, 1, 8, 9, 8 }));
int n,q;
cin>>n>>q;
vector<int> a(n);
for (int i=0; i<n; i++) {
cin>>a[i];
}
vector<int> x, v;
while (q--) {
int i, val;
cin>>i>>val;
x.push_back(i);
v.push_back(val);
}
auto res = countScans(a,x,v);
for (int i: res) cout<<i<<" ";
cout<<endl;
return 0;
}
*/
