Little Monk and Swaps.cpp

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define ld long double
#define pb push_back
#define mkp make_pair
#define pii pair<int, int> 
#define pll pair<long long int, long long int>
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define fi first
#define sc second
#define deb 0

int A[100005], n;
vector<int> v;
multiset<int> se;
set<int> s[100001];

void dfs(int x)
{
	if (x > n) return;
	dfs(2*x);
	v.pb(A[x]);
	dfs(2*x+1);
}

int main()
{
	ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);

	int i, j, k, x, y, z;
	cin >> n;
	for (i = 1; i <= n; ++i) cin >> A[i], se.insert(A[i]);
	dfs(1);
	for (i = 0; i < n; ++i) s[v[i]].insert(i);
	int ans = 0;
	for (i = 0; i < n; ++i) {
		if (v[i] != *se.begin()) {
			x = v[i];
			y = *se.begin();
			z = *(--s[y].end());
			s[y].erase(z);
			s[y].insert(i);
			s[x].erase(i);
			s[x].insert(z);

			swap(v[i], v[z]);
			ans += 1;

		}	
		se.erase(se.begin());
	}
	cout << ans << endl;

	return 0;
}