Untitled

#include "optimization.h"
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> t;

uint32_t cur = 0;
uint32_t a, b;

long long answer = 0;

void merge(int l, int m, int r, int k, vector<t>& a, vector<t>& buffer, vector<long long>& levo_bolshe, vector<long long>& pravo_menshe) {
	int count_in_buffer = 0;
	int left_pointer = l, right_pointer = m + 1;
	for (int i = l; i <= r; i++) {
		if (left_pointer <= m and right_pointer <= r) {
			if (a[left_pointer] <= a[right_pointer]) {
				buffer[i] = a[left_pointer];
				left_pointer++;
			}
			else {	
				count_in_buffer++;
				k==1 ? levo_bolshe[a[right_pointer].first] += (m + 1 - left_pointer) :
					pravo_menshe[a.size() + 1 - a[right_pointer].first] += m + 1 - left_pointer ;

				buffer[i] = a[right_pointer];
				right_pointer++;
				answer += (m + 1 - left_pointer);
			}
		}
		else if (left_pointer <= m) {
			buffer[i] = a[left_pointer];
			left_pointer++;
		

		}
		else if (right_pointer <= r) {
			buffer[i] = a[right_pointer++];
		}
		
	}
	for (int i = l; i <= r; i++) {
		a[i] = buffer[i];
	}
}

void mergesort(int l, int r, int k, vector<t>& a,  vector<t>& buffer, vector<long long>& levo_bolshe, vector<long long>& pravo_menshe) {
	if ((r) <= l) return;
	int m = (l + r) / 2;
	mergesort(l, m, k, a, buffer,  levo_bolshe, pravo_menshe);
	mergesort(m + 1, r, k, a, buffer, levo_bolshe, pravo_menshe);
	merge(l, m, r,  k, a, buffer, levo_bolshe, pravo_menshe);
}




int main() {
	vector<long long> levo_bolshe(100002);
	vector<long long> pravo_menshe(100002);

	vector<t> arr;
	int n = readInt();
	for (int i = 0; i < n; i++) {
		int a = readInt();
		arr.push_back(make_pair(a, i));
	}

	sort(arr.begin(), arr.end(), [](const auto& x, const auto& y) {return x.first < y.first; });

	for (int i = 0; i < arr.size(); i++) {
		arr[i].first = i + 1;
	}

	sort(arr.begin(), arr.end(), [](const auto& x, const auto& y) {return x.second < y.second; });

	vector<t> arr2 = arr;

	for (int i = 0; i < arr.size(); i++) {
		arr2[arr.size()-1-i].first = arr.size() + 1 - arr[i].first;
	}

	vector<t> buffer(arr.size());
	mergesort(0, arr.size() - 1, 1, arr, buffer, levo_bolshe, pravo_menshe);

	mergesort(0, arr2.size() - 1, 2, arr2, buffer, levo_bolshe, pravo_menshe);

	long long sum = 0;

	for (int i = 0; i < arr.size(); i++) {
		sum += levo_bolshe[i] * pravo_menshe[i];
	}

	writeInt(sum);
}