There are $n$ points on a coordinate axis $OX$. The $i$-th point is located at the integer point $x_i$ and has a speed $v_i$. It is guaranteed that no two points occupy the same coordinate. All $n$ points move with the constant speed, the coordinate of the $i$-th point at the moment $t$ ($t$ can be non-integer) is calculated as $x_i + t \cdot v_i$.

Consider two points $i$ and $j$. Let $d(i, j)$ be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points $i$ and $j$ coincide at some moment, the value $d(i, j)$ will be $0$.

Your task is to calculate the value $\sum\limits_{1 \le i < j \le n}$ $d(i, j)$ (the sum of minimum distances over all pairs of points).


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of points.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^8$), where $x_i$ is the initial coordinate of the $i$-th point. It is guaranteed that all $x_i$ are distinct.

The third line of the input contains $n$ integers $v_1, v_2, \dots, v_n$ ($-10^8 \le v_i \le 10^8$), where $v_i$ is the speed of the $i$-th point.


-----Output-----

Print one integer — the value $\sum\limits_{1 \le i < j \le n}$ $d(i, j)$ (the sum of minimum distances over all pairs of points).


-----Examples-----
Input
3
1 3 2
-100 2 3

Output
3

Input
5
2 1 4 3 5
2 2 2 3 4

Output
19

Input
2
2 1
-3 0

Output
0

Source: codeforces | Difficulty: HARD
Tags: Sorting

Data structures

Implementation

Divide and conquer


Solutions:
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left
string = lambda : stdin.readline().strip()
get = lambda : int(stdin.readline().strip())
array = lambda : list(map(int, stdin.readline().strip().split()))
charar = lambda : list(map(str, stdin.readline().strip()))
put = lambda *args: [stdout.write(str(i)) for i in args]
(mod, inf) = (int(1000000000.0 + 7), int(1000000000000000.0))

def solve():
	n = get()
	x = array()
	v = array()
	z = sorted(list(zip(v, x)))
	x.sort()
	s = 0
	for i in range(n):
		s += (bisect_left(x, z[i][1]) + i - n + 1) * z[i][1]
	print(s)
solve()


from os import path
from sys import stdin, stdout
from bisect import bisect_left
if path.exists('inp.txt'):
	stdin = open('inp.txt', 'r')
maxn = 200005
a = []
b = []
fen = [(0, 0) for i in range(maxn)]
res = 0
n = int(stdin.readline())

def update(x, val):
	global fen
	while x > 0:
		fen[x] = (fen[x][0] + val, fen[x][1] + 1)
		x -= x & -x

def get(x, val):
	global n, fen
	A = 0
	B = 0
	while x < n + 2:
		A += fen[x][0]
		B += fen[x][1]
		x += x & -x
	return A - B * val
af = list(map(int, stdin.readline().split()))
ad = list(map(int, stdin.readline().split()))
for i in range(n):
	a.append((af[i], ad[i]))
	b.append(ad[i])
a.sort()
b.sort()
for i in range(n):
	a[i] = (a[i][0], bisect_left(b, a[i][1]) + 1)
for i in range(n - 1, -1, -1):
	res += get(a[i][1], a[i][0])
	update(a[i][1], a[i][0])
print(res)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, X, S):
	si = {}
	ss = list(sorted(set(S)))
	for (i, s) in enumerate(ss):
		si[s] = i
	xs = [(x, si[s]) for (x, s) in zip(X, S)]
	xs.sort()
	bitc = [0 for _ in range(N + 1)]
	bitx = [0 for _ in range(N + 1)]

	def add(index, val):
		while index <= N:
			bitc[index] += 1
			bitx[index] += val
			index |= index + 1

	def get(index):
		(count, xsum) = (0, 0)
		while index >= 0:
			count += bitc[index]
			xsum += bitx[index]
			index = (index & index + 1) - 1
		return (count, xsum)
	ans = 0
	for (x, s) in xs:
		(count, xsum) = get(s)
		ans += count * x - xsum
		add(s, x)
	return ans
N = int(input())
X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]
print(solve(N, X, S))


def main():
	import sys
	input = sys.stdin.readline

	class Bit:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i
	N = int(input())
	X = list(map(int, input().split()))
	V = list(map(int, input().split()))
	info = [(x, v) for (x, v) in zip(X, V)]
	info.sort(key=lambda p: p[0])
	info.sort(key=lambda p: p[1])
	X.sort()
	x2i = {x: i + 1 for (i, x) in enumerate(X)}
	bit_x = Bit(N + 1)
	bit_cnt = Bit(N + 1)
	ans = 0
	for (x, _) in info:
		i = x2i[x]
		ans += bit_cnt.sum(i) * x - bit_x.sum(i)
		bit_x.add(i, x)
		bit_cnt.add(i, 1)
	print(ans)
main()


import operator
import collections
from sys import stdin
N = int(input())
pos = list(map(int, stdin.readline().split()))
speed = list(map(int, stdin.readline().split()))
A = []
for i in range(N):
	A.append((pos[i], speed[i]))
dist = {}
for i in pos:
	dist[i] = 0
A.sort(key=operator.itemgetter(0))
count = [0]

def merge_compare(p, r):
	if p < r:
		q = (r + p) // 2
		merge_compare(p, q)
		merge_compare(q + 1, r)
		merge(p, q, r)

def merge(p, q, r):
	n_1 = q - p + 1
	n_2 = r - q
	temp = []
	L = A[p:q + 1]
	R = A[q + 1:r + 1]
	i = 0
	j = 0
	sum_pos_right = 0
	for (e, f) in R:
		sum_pos_right += e
	while i < n_1 and j < n_2:
		if L[i][1] <= R[j][1]:
			temp.append(L[i])
			count[0] += sum_pos_right - L[i][0] * (n_2 - j)
			i += 1
		else:
			temp.append(R[j])
			sum_pos_right -= R[j][0]
			j += 1
	if i == n_1:
		temp += R[j:]
	else:
		temp += L[i:]
	A[p:r + 1] = temp
merge_compare(0, N - 1)
print(count[0])


def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	ret = 0
	x = a
	while x > 0:
		ret += bit[x]
		x -= x & -1 * x
	return ret
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
vlis = []
for i in v:
	vlis.append(i)
vlis.sort()
vdic = {}
for i in range(n):
	vdic[vlis[i]] = i + 1
xv = []
for i in range(n):
	xv.append([x[i], v[i]])
xv.sort()
ans = 0
BIT = [0] * (n + 1)
BIT2 = [0] * (n + 1)
for i in range(n):
	(x, v) = xv[i]
	ans += x * bitsum(vdic[v], BIT2) - bitsum(vdic[v], BIT)
	bitadd(vdic[v], x, BIT)
	bitadd(vdic[v], 1, BIT2)
print(ans)


from bisect import bisect_right, bisect_left

class BITbisect:

	def __init__(self, InputProbNumbers):
		self.ind_to_co = [-10 ** 18]
		self.co_to_ind = {}
		for (ind, num) in enumerate(sorted(list(set(InputProbNumbers)))):
			self.ind_to_co.append(num)
			self.co_to_ind[num] = ind + 1
		self.max = len(self.co_to_ind)
		self.data = [0] * (self.max + 1)

	def __str__(self):
		retList = []
		for i in range(1, self.max + 1):
			x = self.ind_to_co[i]
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					retList.append(x)
		return '[' + ', '.join([str(a) for a in retList]) + ']'

	def __getitem__(self, key):
		key += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < key:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max or key < 0:
			raise IndexError('BIT index out of range')
		return self.ind_to_co[ind + 1]

	def __len__(self):
		return self._query_sum(self.max)

	def __contains__(self, num):
		if not num in self.co_to_ind:
			return False
		return self.count(num) > 0

	def _query_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def _add(self, i, x):
		while i <= self.max:
			self.data[i] += x
			i += i & -i

	def push(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The pushing number didnt initialized')
		self._add(self.co_to_ind[x], 1)

	def delete(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The deleting number didnt initialized')
		if self.count(x) <= 0:
			raise ValueError('The deleting number doesnt exist')
		self._add(self.co_to_ind[x], -1)

	def count(self, x):
		return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x] - 1)

	def bisect_right(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_right(self.ind_to_co, x) - 1
		return self._query_sum(i)

	def bisect_left(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_left(self.ind_to_co, x)
		if i == 1:
			return 0
		return self._query_sum(i - 1)

class sumBIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0 for _ in range(self.N + 1)]

	def __str__(self):
		ret = []
		for i in range(1, self.N + 1):
			ret.append(self.__getitem__(i))
		return '[' + ', '.join([str(a) for a in ret]) + ']'

	def __getitem__(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.N:
			self.bit[i] += x
			i += i & -i
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
	N = int(input())
	X = list(map(int, input().split()))
	V = list(map(int, input().split()))
	XV = [(x, v) for (x, v) in zip(X, V)]
	XV.sort()
	XV.sort(key=itemgetter(1))
	co_to_ind1 = {}
	for (i, (x, v)) in enumerate(XV):
		co_to_ind1[x] = i + 1
	XV.sort()
	sumbit = sumBIT(N + 1)
	bit = sumBIT(N + 1)
	ans = 0
	for (x, v) in XV:
		ind1 = co_to_ind1[x]
		count = bit[ind1]
		s = sumbit[ind1]
		ans += count * x - s
		bit.add(ind1, 1)
		sumbit.add(ind1, x)
	print(ans)
main()


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
s = list(map(int, input().split()))
d1 = defaultdict(list)
for i in range(n):
	d1[l[i]].append(s[i])
s.sort()
d = defaultdict(list)
for i in range(n):
	d[s[i]].append(i)
for i in d:
	d[i].sort()
	d[i] = deque(d[i])
l.sort()
u = [0] * n
u1 = [0] * n
s = SegmentTree(u)
s1 = SegmentTree(u1)
ans = 0
for i in range(n):
	sp = d1[l[i]][-1]
	d1[l[i]].pop()
	pos = d[sp][0]
	d[sp].popleft()
	ans += s.query(0, pos - 1) * l[i] - s1.query(0, pos - 1)
	s.__setitem__(pos, 1)
	s1.__setitem__(pos, l[i])
print(ans)


class Points:

	def __init__(self, x=0, v=0):
		(self.x, self.v) = (x, v)

class Fenwick_tree:

	def __init__(self, n=0):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, value):
		while x <= self.n:
			self.bit[x] += value
			x += x & -x

	def get(self, x):
		sum = 0
		while x > 0:
			sum += self.bit[x]
			x -= x & -x
		return sum
(n, x, v) = (int(input()), list(map(int, input().split())), list(map(int, input().split())))
a = [Points(x[i], v[i]) for i in range(n)]
a.sort(key=lambda value: value.x)
v = [a[i].v for i in range(n)]
v.sort()
data = {}
cnt = 1
for i in range(n):
	if not data.__contains__(v[i]):
		data[v[i]] = cnt
		cnt += 1
cnt = Fenwick_tree(n)
sum = Fenwick_tree(n)
(res, i) = (0, 0)
for i in range(n):
	a[i].v = data[a[i].v]
	res += a[i].x * cnt.get(a[i].v) - sum.get(a[i].v)
	cnt.update(a[i].v, 1)
	sum.update(a[i].v, a[i].x)
print(res)


INF = 10 ** 10

def main():
	n = get_int()
	points = get_list()
	speeds = get_list()
	point_indexes = dict()
	sorted_indexes = dict()
	for (i, ele) in enumerate(points):
		point_indexes[ele] = i
	for (i, ele) in enumerate(sorted(points)):
		sorted_indexes[ele] = i
	points.sort(reverse=True)
	points.sort(key=lambda x: speeds[point_indexes[x]], reverse=True)
	stree = SegTreeSum(n)
	scount = SegTreeSum(n)
	res = 0
	for i in points:
		index = sorted_indexes[i]
		res += stree.query(index, n - 1) - i * scount.query(index, n - 1)
		stree.modify(index, i)
		scount.modify(index, 1)
	print(res)

class SegTreeSum:

	def __init__(self, size):
		self.n = 1 << size.bit_length()
		self.li = [0] * (self.n << 1)

	def modify(self, index, ele):
		index += self.n
		self.li[index] = ele
		while index > 1:
			self.li[index >> 1] = self.li[index] + self.li[index ^ 1]
			index >>= 1

	def get(self, index):
		return self.li[self.n + index]

	def query(self, l, r):
		res = 0
		(l, r) = (l + self.n, r + self.n)
		while l <= r:
			if l & 1 == 1:
				res += self.li[l]
			if r & 1 != 1:
				res += self.li[r]
			l = l + 1 >> 1
			r = r - 1 >> 1
		return res
import sys
from collections import defaultdict, Counter, deque
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
main()
print(*out, sep='\n')


import sys
input = sys.stdin.readline
n = int(input())
X = list(map(int, input().split()))
V = list(map(int, input().split()))
XV = [(X[i], V[i]) for i in range(n)]
compression_dict_v = {a: ind + 2 for (ind, a) in enumerate(sorted(set(V)))}
XV = [(XV[i][0], compression_dict_v[XV[i][1]]) for i in range(n)]
XV.sort(reverse=True)
LEN = len(compression_dict_v) + 3
BIT1 = [0] * (LEN + 1)

def update1(v, w):
	while v <= LEN:
		BIT1[v] += w
		v += v & -v

def getvalue1(v):
	ANS = 0
	while v != 0:
		ANS += BIT1[v]
		v -= v & -v
	return ANS
BIT2 = [0] * (LEN + 1)

def update2(v, w):
	while v <= LEN:
		BIT2[v] += w
		v += v & -v

def getvalue2(v):
	ANS = 0
	while v != 0:
		ANS += BIT2[v]
		v -= v & -v
	return ANS
ANS = 0
for (x, v) in XV:
	ANS += getvalue2(LEN) - getvalue2(v - 1) - (getvalue1(LEN) - getvalue1(v - 1)) * x
	update1(v, 1)
	update2(v, x)
print(ANS)


import math
import sys
from collections import defaultdict, Counter
from itertools import groupby
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, val):
		while i <= self.size:
			self.tree[i] += val
			i += i & -i

def main():
	n = ri()
	x = rl()
	v = rl()
	pts = [(xi, vi) for (xi, vi) in zip(x, v)]
	pts.sort(key=lambda a: (a[1], a[0]))
	comprX = {val: i + 1 for (i, val) in enumerate(sorted(x))}
	bit_x = Bit(n + 1)
	bit_cnt = Bit(n + 1)
	res = 0
	for (xi, vi) in pts:
		compr = comprX[xi]
		res += bit_cnt.sum(compr) * xi - bit_x.sum(compr)
		bit_x.add(compr, xi)
		bit_cnt.add(compr, 1)
	print(res)
main()


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:

	def __init__(self, n):
		n += 1
		nv = 1
		while nv < n:
			nv *= 2
		self.size = nv
		self.tree = [0] * nv

	def sum(self, i):
		s = 0
		i += 1
		while i > 0:
			s += self.tree[i - 1]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i - 1] += x
			i += i & -i

	def get(self, l, r=None):
		if r is None:
			r = l + 1
		res = 0
		if r:
			res += self.sum(r - 1)
		if l:
			res -= self.sum(l - 1)
		return res

	def update(self, i, x):
		self.add(i, x - self.get(i))

def compress(S):
	(zipped, unzipped) = ({}, {})
	for (i, a) in enumerate(sorted(S)):
		zipped[a] = i
		unzipped[i] = a
	return (zipped, unzipped)
N = INT()
A = LIST()
B = LIST()
BA = list(zip(B, A))
BA.sort()
(zipped, _) = compress(set(A))
bit1 = BIT(N)
bit2 = BIT(N)
ans = 0
for (b, a) in BA:
	sm = bit1.sum(zipped[a])
	cnt = bit2.sum(zipped[a])
	ans += cnt * a - sm
	bit1.add(zipped[a], a)
	bit2.add(zipped[a], 1)
print(ans)


import sys
input = sys.stdin.readline
from heapq import heappush, heappop, heapify

def query(f, i):
	ret = [0, 0]
	while i:
		ret[0] += f[i][0]
		ret[1] += f[i][1]
		i -= i & -i
	return ret

def update(f, i, d):
	n = len(f)
	while i < n:
		f[i][0] += d[0]
		f[i][1] += d[1]
		i += i & -i
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
a = [()] * (n + 1)
for i in range(1, n + 1):
	a[i] = (x[i - 1], v[i - 1])
a.sort()
f = [[0, 0] for i in range(n + 1)]
for i in range(1, n + 1):
	update(f, i, [a[i][0], 1])
b = []
for i in range(1, n + 1):
	b.append((-a[i][1], -i))
heapify(b)
ans = 0
while b:
	(v, i) = heappop(b)
	(v, i) = (-v, -i)
	x = a[i][0]
	if i > 1:
		(sum, cnt) = query(f, i - 1)
		ans += x * cnt - sum
	update(f, i, [-x, -1])
print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RangeMinimumQuery:

	def __init__(self, n, inf=float('inf')):
		self.n0 = 2 ** (n - 1).bit_length()
		self.inf = inf
		self.data = [self.inf] * (2 * self.n0)
		self.cnt = [0] * (2 * self.n0)

	def query(self, l, r):
		l += self.n0
		r += self.n0
		res = 0
		cnt = 0
		while l < r:
			if r & 1:
				r -= 1
				res += self.data[r - 1]
				cnt += self.cnt[r - 1]
			if l & 1:
				res += self.data[l - 1]
				cnt += self.cnt[l - 1]
				l += 1
			l >>= 1
			r >>= 1
		return (res, cnt)

	def update(self, i, x):
		i += self.n0 - 1
		self.data[i] += x
		self.cnt[i] += 1
		while i:
			i = ~-i // 2
			self.data[i] = self.data[2 * i + 1] + self.data[2 * i + 2]
			self.cnt[i] = self.cnt[2 * i + 1] + self.cnt[2 * i + 2]
n = int(input())
xs = list(map(int, input().split()))
vs = list(map(int, input().split()))
xv = [[x, v] for (x, v) in zip(xs, vs)]
xv.sort()
d = sorted(set(vs))
dd = {j: i for (i, j) in enumerate(d)}
m = len(dd)
RSQ = RangeMinimumQuery(m, 0)
ans = 0
for (x, v) in xv:
	nv = dd[v]
	(su, cnt) = RSQ.query(0, nv + 1)
	ans += cnt * x - su
	RSQ.update(nv, x)
print(ans)


import sys
input = sys.stdin.readline

def getsum(BITTree, i):
	s = 0
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	while i <= n:
		BITTree[i] += v
		i += i & -i
n = int(input())
x = [int(i) for i in input().split() if i != '\n']
v = [int(i) for i in input().split() if i != '\n']
for i in range(n):
	v[i] = [v[i], i]
v.sort()
pos = dict()
(store, prev) = (1, v[0][0])
for i in range(n):
	if i > 0:
		if prev == v[i][0]:
			pos[x[v[i][1]]] = store
		else:
			store += 1
			pos[x[v[i][1]]] = store
			prev = v[i][0]
	else:
		pos[x[v[i][1]]] = store
sort = sorted(pos.keys())
bit = [0] * (n + 1)
ind = [0] * (n + 1)
(ans, count, diff) = (0, 0, 0)
length = max(sort)
total = 0
for i in range(len(sort) - 1, -1, -1):
	count = getsum(bit, pos[sort[i]] - 1)
	diff = getsum(ind, pos[sort[i]] - 1)
	if i < n - 1:
		total += (sort[i + 1] - sort[i]) * (n - 1 - i)
		ans += total - (diff - count * sort[i])
	updatebit(bit, len(bit) - 1, pos[sort[i]], 1)
	updatebit(ind, len(ind) - 1, pos[sort[i]], sort[i])
print(int(ans))


import bisect

class Bit:

	def __init__(self, n):
		self.bit = [0 for i in range(0, n)]

	def add(self, pos, x):
		while pos < len(self.bit):
			self.bit[pos] += x
			pos = pos | pos + 1

	def query(self, pos):
		res = 0
		while pos > 0:
			res += self.bit[pos - 1]
			pos = pos & pos - 1
		return res
n = int(input())
x = [int(i) for i in input().split()]
v = [int(i) for i in input().split()]
r = [i for i in range(n)]
r.sort(key=lambda i: x[i])
unique = sorted(list(set(v)))
(tree1, tree2) = (Bit(len(unique)), Bit(len(unique)))
ans = 0
for i in r:
	ii = bisect.bisect_left(unique, v[i])
	count = tree1.query(ii + 1)
	dsum = tree2.query(ii + 1)
	ans += count * x[i] - dsum
	tree1.add(ii, 1)
	tree2.add(ii, x[i])
print(ans)


import sys
input = sys.stdin.readline
from heapq import heappush, heappop, heapify

def query(f, i):
	ret = 0
	while i:
		ret += f[i]
		i -= i & -i
	return ret

def update(f, i, d):
	n = len(f)
	while i < n:
		f[i] += d
		i += i & -i
n = int(input())
X = list(map(int, input().split()))
V = list(map(int, input().split()))
r = list(range(n))
r.sort(key=lambda i: X[i])
f = [0] * (n + 1)
f2 = [0] * (n + 1)
b = []
for (i, k) in enumerate(r):
	b.append((V[k], i))
heapify(b)
ans = 0
while b:
	(v, i) = heappop(b)
	x = X[r[i]]
	sum = query(f, i)
	cnt = query(f2, i)
	ans += x * cnt - sum
	update(f, i + 1, x)
	update(f2, i + 1, 1)
print(ans)


def add(sms, cns, n, v, x):
	while v < n:
		sms[v] += x
		cns[v] += 1
		v += v & ~(v - 1)

def sumtoo(sms, cns, v):
	sm = 0
	cn = 0
	while v > 0:
		sm += sms[v]
		cn += cns[v]
		v -= v & ~(v - 1)
	return (sm, cn)

def go():
	n = int(input())
	x = list(map(int, input().split()))
	v = list(map(int, input().split()))
	sv = sorted(set(v))
	sv = {v: k for (k, v) in enumerate(sv, 1)}
	v = [sv[v] for v in v]
	a = sorted(((xx, vv) for (xx, vv) in zip(x, v)), reverse=True)
	len_sv = len(sv) + 1
	sms = [0] * len_sv
	cns = [0] * len_sv
	res = 0
	sx = 0
	for (cnt, (xx, vv)) in enumerate(a):
		(sm, cn) = sumtoo(sms, cns, vv - 1)
		(sm, cn) = (sx - sm, cnt - cn)
		res += sm - xx * cn
		add(sms, cns, len_sv, vv, xx)
		sx += xx
	return res
print(go())


import sys
input = sys.stdin.readline
import bisect

def query(f, i):
	ret = 0
	while i:
		ret += f[i]
		i -= i & -i
	return ret

def update(f, i, d):
	n = len(f)
	while i < n:
		f[i] += d
		i += i & -i
n = int(input())
X = list(map(int, input().split()))
V = list(map(int, input().split()))
r = list(range(n))
r.sort(key=lambda i: X[i])
vlist = sorted(set(V))
f = [0] * (len(vlist) + 1)
f2 = [0] * (len(vlist) + 1)
ans = 0
for i in r:
	(x, v) = (X[i], V[i])
	ii = bisect.bisect_left(vlist, v)
	sm = query(f, ii + 1)
	cnt = query(f2, ii + 1)
	ans += x * cnt - sm
	update(f, ii + 1, x)
	update(f2, ii + 1, 1)
print(ans)


from operator import itemgetter

class BIT:

	def __init__(self, size):
		self.table = [0 for _ in range(size + 2)]
		self.size = size

	def Sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= i & -i
		return s

	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += i & -i
		return
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
y = sorted([(xx, vv) for (xx, vv) in zip(x, v)], key=itemgetter(1))
z = [[y[0][0], 1]]
for i in range(1, n):
	if y[i][1] == y[i - 1][1]:
		z.append([y[i][0], z[-1][1]])
	else:
		z.append([y[i][0], z[-1][1] + 1])
z.sort()
(b_sigma, b_num) = (BIT(n + 2), BIT(n + 2))
ans = 0
for (x, v) in z:
	num = b_num.Sum(v)
	ans += x * num - b_sigma.Sum(v)
	b_num.PointAdd(v, 1)
	b_sigma.PointAdd(v, x)
print(ans)


import io
import os
from collections import Counter, defaultdict, deque, namedtuple

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

def solve(N, X, V):
	indices = sorted(range(N), key=lambda i: X[i])
	X = [X[i] for i in indices]
	V = [V[i] for i in indices]
	BIL = 10 ** 9
	vIndices = sorted(range(N), key=lambda i: V[i] * BIL + X[i])
	indicesByV = {originalIndex: sortedIndex for (sortedIndex, originalIndex) in enumerate(vIndices)}
	segTreeTotal = SegmentTree([0 for i in range(N)], 0, lambda a, b: a + b)
	segTreeCount = SegmentTree([0 for i in range(N)], 0, lambda a, b: a + b)
	ans = 0
	for j in range(N):
		index = indicesByV[j]
		count = segTreeCount.query(0, index)
		totalXi = segTreeTotal.query(0, index)
		ans += X[j] * count - totalXi
		segTreeCount[index] = 1
		segTreeTotal[index] = X[j]
	return ans

def solveBrute(N, X, V):
	indices = sorted(range(N), key=lambda i: X[i])
	X = [X[i] for i in indices]
	V = [V[i] for i in indices]
	ans = 0
	for j in range(N):
		xj = X[j]
		vj = V[j]
		total = 0
		totalXi = 0
		count = 0
		for i in range(j):
			xi = X[i]
			vi = V[i]
			assert xi <= xj
			if vi <= vj:
				total += xj - xi
				totalXi += xi
				count += 1
		print(j, X[j], count, totalXi)
		assert total == X[j] * count - totalXi
		ans += total
	return ans
if False:
	import random
	random.seed(0)
	N = 200000
	for i in range(1):
		X = [random.randint(0, 10) for i in range(N)]
		V = [random.randint(0, 10) for i in range(N)]
		ans = solve(N, X, V)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
ans = solve(N, X, V)
print(ans)


class SegmentTree:

	def __init__(self, N, func, initialRes=0):
		self.f = func
		self.N = N
		self.tree = [0 for _ in range(4 * self.N)]
		self.initialRes = initialRes

	def updateTreeNode(self, idx, value):
		self.tree[idx + self.N] = value
		idx += self.N
		i = idx
		while i > 1:
			self.tree[i >> 1] = self.f(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query(self, l, r):
		r += 1
		res = self.initialRes
		l += self.N
		r += self.N
		while l < r:
			if l & 1:
				res = self.f(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.f(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def getMaxSegTree(arr):
	return SegmentTree(arr, lambda a, b: max(a, b), initialRes=-float('inf'))

def getMinSegTree(arr):
	return SegmentTree(arr, lambda a, b: min(a, b), initialRes=float('inf'))

def getSumSegTree(arr):
	return SegmentTree(arr, lambda a, b: a + b, initialRes=0)

def main():
	n = int(input())
	xes = readIntArr()
	ves = readIntArr()
	xes2 = list(sorted(xes))
	xTox2Map = dict()
	for (i, x) in enumerate(xes2):
		xTox2Map[x] = i
	arr = []
	for i in range(n):
		arr.append([xes[i], xTox2Map[xes[i]], ves[i]])
	arr.sort(key=lambda x: (x[2], x[0]))
	st = getSumSegTree(n)
	stCnts = getSumSegTree(n)
	ans = 0
	for (originalX, compressedX, v) in arr:
		smallerSums = st.query(0, compressedX)
		smallerCounts = stCnts.query(0, compressedX)
		ans += originalX * smallerCounts - smallerSums
		st.updateTreeNode(compressedX, originalX)
		stCnts.updateTreeNode(compressedX, 1)
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


class Points:

	def __init__(self, x=0, v=0):
		(self.x, self.v) = (x, v)

class Fenwick_tree:

	def __init__(self, n=0):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, value):
		while x <= self.n:
			self.bit[x] += value
			x += x & -x

	def get(self, x):
		sum = 0
		while x > 0:
			sum += self.bit[x]
			x -= x & -x
		return sum
(n, x, v) = (int(input()), list(map(int, input().split())), list(map(int, input().split())))
a = [Points(x[i], v[i]) for i in range(n)]
a.sort(key=lambda value: value.x)
temp = sorted(set(v))
mp = {v: k for (k, v) in enumerate(temp, 1)}
cnt = Fenwick_tree(n)
sum = Fenwick_tree(n)
(res, i) = (0, 0)
for i in range(n):
	a[i].v = mp[a[i].v]
	res += a[i].x * cnt.get(a[i].v) - sum.get(a[i].v)
	cnt.update(a[i].v, 1)
	sum.update(a[i].v, a[i].x)
print(res)


import math
import bisect

class Fenwick:

	def __init__(self, n):
		self.data = [[0, 0] for i in range(n)]

	def update(self, pos, dist):
		while pos < len(self.data):
			self.data[pos][0] += 1
			self.data[pos][1] += dist
			pos = pos | pos + 1

	def query(self, pos):
		ans = [0, 0]
		while pos > 0:
			ans[0] += self.data[pos - 1][0]
			ans[1] += self.data[pos - 1][1]
			pos = pos & pos - 1
		return ans

def rints():
	return list(map(int, input().split()))
n = int(input())
x = rints()
v = rints()
ascDist = list(range(n))
ascDist.sort(key=lambda i: x[i])
uniqueSpeeds = sorted(list(set(v)))
tree = Fenwick(len(uniqueSpeeds))
ans = 0
for i in ascDist:
	speedId = bisect.bisect_left(uniqueSpeeds, v[i])
	(count, dsum) = tree.query(speedId + 1)
	ans += count * x[i] - dsum
	tree.update(speedId, x[i])
print(ans)


class BIT:

	def __init__(self, array):
		self.n = len(array)
		self.bit = [0] + array
		self.build()

	def build(self):
		for i in range(1, self.n):
			if i + (i & -i) > self.n:
				continue
			self.bit[i + (i & -i)] += self.bit[i]

	def _sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, val):
		i += 1
		while i <= self.n:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, l, r):
		return self._sum(r) - self._sum(l)
from operator import itemgetter
import sys
input = sys.stdin.readline
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
sorted_x = sorted(x)
bit = BIT(sorted_x)
bit_ind = BIT([1] * n)
to_ind = {v: i for (i, v) in enumerate(sorted_x)}
info = [None] * n
for i in range(n):
	info[i] = (v[i] + 10 ** 18, x[i])
info = sorted(info, key=itemgetter(1), reverse=True)
info = sorted(info, key=itemgetter(0), reverse=True)
ans = 0
for i in range(n):
	(_, pos) = info[i]
	ind = to_ind[pos]
	sum_ = bit.get_sum(0, ind)
	num = bit_ind.get_sum(0, ind)
	ans += num * pos - sum_
	bit.add(ind, -pos)
	bit_ind.add(ind, -1)
print(ans)


class Fenwick:

	def __init__(self, size):
		self.tree = [0] * size
		self.size = size

	def add(self, idx, delta):
		while idx < self.size:
			self.tree[idx] += delta
			idx = idx + 1 | idx

	def getp(self, right):
		res = 0
		while right != -1:
			res += self.tree[right]
			right = (right + 1 & right) - 1
		return res

	def get(self, left, right):
		if left > right:
			return 0
		return self.getp(right) - self.getp(left - 1)
n = int(input())
X = list(map(int, input().split()))
V = list(map(int, input().split()))
XV = list(zip(X, V))
XV.sort()
order = list(range(n))
order.sort(key=lambda i: XV[i][1])
ans = 0
for i in range(n):
	ans += XV[n - 1 - i][0] * (n - 1 - 2 * i)
fw = Fenwick(n)
fwcount = Fenwick(n)
for i in order:
	ans -= fw.get(i + 1, n - 1) - fwcount.get(i + 1, n - 1) * XV[i][0]
	fw.add(i, XV[i][0])
	fwcount.add(i, 1)
print(ans)


import bisect

def getsum(tree, i):
	s = 0
	i += 1
	while i > 0:
		s += tree[i]
		i -= i & -i
	return s

def updatebit(tree, n, i, v):
	i += 1
	while i <= n:
		tree[i] += v
		i += i & -i
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
p = [[x[i], v[i]] for i in range(len(x))]
vs = sorted(list(set(v)))
p = sorted(p, key=lambda i: i[0])
l = len(vs)
cnt = [0] * (l + 1)
xs = [0] * (l + 1)
ans = 0
for pnt in p:
	pos = bisect.bisect_left(vs, pnt[1])
	ans += getsum(cnt, pos) * pnt[0] - getsum(xs, pos)
	updatebit(cnt, l, pos, 1)
	updatebit(xs, l, pos, pnt[0])
print(ans)


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
mod = int(1000000000.0) + 7

def update(BIT, v, w):
	while v <= n:
		BIT[v] += w
		v += v & -v

def getvalue(BIT, v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS

def bisect_on_BIT(BIT, x):
	if x <= 0:
		return 0
	ANS = 0
	h = 1 << n - 1
	while h > 0:
		if ANS + h <= n and BIT[ANS + h] < x:
			x -= BIT[ANS + h]
			ANS += h
		h //= 2
	return ANS + 1
n = int(data())
x = mdata()
v = mdata()
a = [[v[i], x[i]] for i in range(n)]
a.sort()
s = [0] * (n + 1)
cnt = [0] * (n + 1)
pos = dd(int)
for i in range(n):
	pos[a[i][1]] = i + 1
for i in range(n):
	update(s, i + 1, a[i][1])
	update(cnt, i + 1, 1)
ans = 0
x.sort()
for i in range(n):
	ind = pos[x[i]]
	ans += getvalue(s, n) - getvalue(s, ind) - (getvalue(cnt, n) - getvalue(cnt, ind)) * x[i]
	update(s, ind, -x[i])
	update(cnt, ind, -1)
out(ans)


import heapq
import sys
input = sys.stdin.readline

def make_tree(n):
	tree = [0] * (n + 1)
	return tree

def get_sum(i, tree):
	s = 0
	while i > 0:
		s += tree[i]
		i -= i & -i
	return s

def add(i, x, tree):
	while i <= n:
		tree[i] += x
		i += i & -i
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
u = list(set(v))
u.sort(reverse=True)
m = len(u)
d = dict()
for i in range(m):
	d[u[i]] = i + 2
tree = make_tree(n + 5)
cnt = make_tree(n + 5)
ans = 0
h = []
for i in range(n):
	heapq.heappush(h, (x[i], i))
sx = []
while h:
	(xi, i) = heapq.heappop(h)
	sx.append(xi)
	vi = v[i]
	di = d[vi]
	ans -= get_sum(di - 1, cnt) * xi - get_sum(di - 1, tree)
	add(di, xi, tree)
	add(di, 1, cnt)
for i in range(n - 1):
	ans += (i + 1) * (n - i - 1) * (sx[i + 1] - sx[i])
print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict

def compress(l):
	l = list(set(l))
	l.sort()
	idx = defaultdict(int)
	c = 0
	for li in l:
		idx[li] = c
		c += 1
	return idx

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def acc(self, i):
		i += 1
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
xv = [(xi, vi) for (xi, vi) in zip(x, v)]
xv.sort(key=lambda t: t[0])
idx = compress(v)
sum_bit = BIT(len(idx))
cnt_bit = BIT(len(idx))
ans = 0
for (xi, vi) in xv:
	ans += cnt_bit.acc(idx[vi]) * xi - sum_bit.acc(idx[vi])
	sum_bit.add(idx[vi], xi)
	cnt_bit.add(idx[vi], 1)
print(ans)


def add(bit, x, v):
	while x < len(bit):
		bit[x] += v
		x += x & -x

def query(bit, x):
	ans = 0
	while x > 0:
		ans += bit[x]
		x -= x & -x
	return ans

def relabel(arr):
	srt = sorted(set(arr))
	mp = {v: k for (k, v) in enumerate(srt, 1)}
	arr = [mp[a] for a in arr]
	return arr
n = int(input())
x = list(map(int, input().split()))
v = relabel(list(map(int, input().split())))
arr = sorted(list(zip(x, v)))
ans = 0
bitSum = [0] * (n + 1)
bitCnt = [0] * (n + 1)
for (x, v) in arr:
	ans += query(bitCnt, v) * x - query(bitSum, v)
	add(bitSum, v, x)
	add(bitCnt, v, 1)
print(ans)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 3
		self.table = [0] * (self.n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

def main():
	n = II()
	xx = LI()
	vv = LI()
	itox = list(sorted(set(xx)))
	xtoi = {x: i for (i, x) in enumerate(itox)}
	vx = [(v, x) for (x, v) in zip(xx, vv)]
	cnt = BitSum(len(itox))
	val = BitSum(len(itox))
	ans = 0
	for (v, x) in sorted(vx):
		i = xtoi[x]
		if i:
			ans += cnt.sum(i - 1) * x - val.sum(i - 1)
		cnt.add(i, 1)
		val.add(i, x)
	print(ans)
main()


import bisect

class ft:

	def __init__(self, n):
		self.a = [0] * 200000
		self.n = n

	def qry(self, r):
		ret = 0
		while r >= 0:
			ret += self.a[r]
			r = (r & r + 1) - 1
		return ret

	def upd(self, i, v):
		while i < self.n:
			self.a[i] += v
			i = i | i + 1
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
f0 = ft(n)
f1 = ft(n)
a1 = [[] for _ in range(n)]
for i in range(n):
	a1[i].append(x[i])
	a1[i].append(v[i])
a1.sort()
v.sort()
ans = 0
for i in range(n):
	p = bisect.bisect_left(v, a1[i][1])
	ans += f0.qry(p) * a1[i][0] - f1.qry(p)
	f0.upd(p, 1)
	f1.upd(p, a1[i][0])
print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)
n = inp()
X = inpl()
V = inpl()
d = {}
dd = {}
for (i, x) in enumerate(sorted(X)):
	d[x] = i
	dd[i] = x
for (i, x) in enumerate(X):
	X[i] = d[x]
xv = [(x, v) for (x, v) in zip(X, V)]
xv.sort(key=lambda x: x[0], reverse=True)
xv.sort(key=lambda x: x[1], reverse=True)
cnt_bit = BIT(n + 10)
sum_bit = BIT(n + 10)
res = 0
for (x, _) in xv:
	res += sum_bit.get(x, n + 5) - cnt_bit.get(x, n + 5) * dd[x]
	sum_bit.add(x + 1, dd[x])
	cnt_bit.add(x + 1, 1)
print(res)


import bisect
import sys

class ft:

	def __init__(self, n):
		self.a = [0] * 200000
		self.n = n

	def qry(self, r):
		ret = 0
		while r >= 0:
			ret += self.a[r]
			r = (r & r + 1) - 1
		return ret

	def upd(self, i, v):
		while i < self.n:
			self.a[i] += v
			i = i | i + 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
n = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
f0 = ft(n)
f1 = ft(n)
a1 = [[] for _ in range(n)]
for i in range(n):
	a1[i].append(x[i])
	a1[i].append(v[i])
a1.sort()
v.sort()
ans = 0
for i in range(n):
	p = bisect.bisect_left(v, a1[i][1])
	ans += f0.qry(p) * a1[i][0] - f1.qry(p)
	f0.upd(p, 1)
	f1.upd(p, a1[i][0])
print(ans)