#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long len[N]; 
int n;

// 预处理len数组，只算一次
void pre() {
	len[0] = 0;
	for (int i = 1; i <= 100000; i++) {
		len[i] = 2 * len[i - 1] + (i + 2);
		if (len[i] > 1e18) break; // 防止溢出
	}
}

// 找到包含n的最小k
int check(long long x) {
	int i = 1;
	while (len[i] < x) i++;
	return i;
}

void f(int k, long long pos) {
	long long L = len[k - 1];
	// 情况1：在左半段 S_{k-1}
	
	// 情况2：中间m
	
	// 情况3：中间o串
	
	// 情况4：右半段 S_{k-1}，减去左侧总长度
	
}

int main() {
	pre();
	cin >> n;
	int k = check(n);
	f(k, n);
	return 0;
}

int dx[] = {-1, 0, 1, 0, 0};

int dy[] = {0, 1, 0, -1, 0};
int ans = 1e9; // 存最小修改次数

// x,y 当前的点， k 是修改次数
void f(int x, int y, int k) {
	// 当前的修改次数已经超过了之前的最优
	// 直接不要, 最优性减枝
	if (k >= ans)
		return ;
	if (check()) {   // check 检查所有的是否变为 1
		ans = min(ans, k);
		return ;
	}
	// 没有满足全开
	if (x > 3)
		return ;
	int nx, ny;
	if (y >= 3)
		nx = x + 1, y = 1;
	else
		nx = x, ny = y + 1;
	dfs(nx, ny, k);   // 当前点不修改
	// 当前点修改
	for (int i = 0; i < 5; i++)
		a[x + dx[i]][y + dy[i]] = !a[x + dx[i]][y + dy[i]];
	dfs(nx, ny, k + 1);
	// 回溯
	for (int i = 0; i < 5; i++)
		a[x + dx[i]][y + dy[i]] = !a[x + dx[i]][y + dy[i]];
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N], tmp[N];
int res;

void msort(int l, int r) {
	// 分结束什么情况？只剩一个
	if (l >= r)
		return ;
	int mid = (l + r) / 2;
	msort(l, mid), msort(mid + 1, r);
	// 合并  [l, mid] , [mid+1, r]
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j])
			tmp[k++] = a[i++];
		else
			res += mid - i + 1, tmp[k++] = a[j++];
	}
	// 还有没放完的部分, 两个循环肯定会执行一个，
	while (i <= mid)
		tmp[k++] = a[i++];
	while (j <= r)
		tmp[k++] = a[j++];
	// 复制会原数组
	for (int i = l, j = 0; i <= r; j++, i++)
		a[i] = tmp[j];
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	msort(1, n);
	cout << res;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, a[N];

void qsort(int a[], int l, int r) {
	if (l >= r) return;
	// 取左端点 q[l] 会被卡掉 两个点
	int x = a[(l + r) / 2], i = l - 1, j = r + 1;
	while (i < j) {
		// 这里先进行了 i++操作，所以上面 i =l -1
		do i++ ;
		while (a[i] < x);
		do j--;
		while (a[j] > x);
		// 当两个点还没有相遇，那就交换
		if (i < j) swap(a[i], a[j]);
	}
	// 分治
	qsort(a, l, j);
	qsort(a, j + 1, r);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	qsort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	return 0;
}

// 分治， 分而治之
// 大的，转化成几个小的部分
// 快速排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
// 找到分界点
int partition(int l, int r) {
	int x = a[(l + r) / 2], i = l - 1, j = r + 1;
	while (i < j) {
		do+
		`..
			i++;
		while (a[i] < x);
		do
			j--;
		while (a[j] > x);
		if (i < j)
			swap(a[i], a[j]);
	}
	return j;
}
int qsort(int l, int r, int k) {
	if (l == r)
		return a[l];
	int j = partition(l, r);
	int cnt = j - l + 1; // 左边的元素个数
	if (k <= cnt)
		return qsort(l, j, k);
	else
		return qsort(j + 1, r, k - cnt);
}
// 去重 ， 调用 qsort