There is an integer array $\boldsymbol{d}$ which does not contain more than two elements of the same value. How many distinct ascending triples ($d[i]<d[j]<d[k],i<j<k$) are present? 

Input format 

The first line contains an integer, $N$, denoting the number of elements in the array. This is followed by a single line, containing $N$ space-separated integers. Please note that there are no leading spaces before the first number, and there are no trailing spaces after the last number.

Output format: 

A single integer that denotes the number of distinct ascending triplets present in the array.

Constraints: 

$N\leq10^5$ 

Every element of the array is present at most twice. 

Every element of the array is a 32-bit non-negative integer.

Sample input:  

6  
1 1 2 2 3 4  

Sample output:  

4

Explanation 

The distinct triplets are 

(1,2,3) 

(1,2,4) 

(1,3,4) 

(2,3,4)

The elements of the array might not be sorted. Make no assumptions of the same.

Source: hackerrank | Difficulty: HARD
Tags: Data structures


Solutions:
root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


from bisect import insort
from bisect import bisect_left
from bisect import bisect
temp = input()
nums = list(map(int, input().strip().split(' ')))
values = []
values_set = set()
left_lens = {}
last_occurence = {}
for (i, n) in enumerate(nums):
	diff = 0
	if n in last_occurence:
		diff = left_lens[last_occurence[n]]
	pos = bisect_left(values, n)
	left_lens[i] = pos - diff
	last_occurence[n] = i
	if n not in values_set:
		values_set.add(n)
		insort(values, n)
values = []
values_set = set()
right_lens = {}
combinations = 0
for (i, n) in enumerate(reversed(nums), start=1):
	i = len(nums) - i
	pos = len(values) - bisect(values, n)
	right_lens[i] = pos
	if n not in values_set:
		values_set.add(n)
		insort(values, n)
	combinations += left_lens[i] * right_lens[i]
print(combinations)


import math
import sys

class SegmentTree:

	def __init__(self, size):
		self.size = size
		max_size = 2 ** math.ceil(math.log2(size))
		self.__nodes = [0] * (max_size * 2)

	def __node_idx(self, idx):
		assert idx >= 0 and idx < len(self.__nodes) / 2
		return int(len(self.__nodes) / 2) + idx

	def update(self, idx, value):
		assert idx >= 0 and idx < self.size
		node_idx = self.__node_idx(idx)
		diff = value - self.__nodes[node_idx]
		while node_idx >= 1:
			self.__nodes[node_idx] += diff
			node_idx = math.floor(node_idx / 2)

	def inc(self, idx, amount=1):
		assert idx >= 0 and idx < self.size
		node_idx = self.__node_idx(idx)
		self.update(idx, self.__nodes[node_idx] + amount)

	def sum(self, left_idx=None, right_idx=None):
		if left_idx is None:
			left_idx = 0
		if right_idx is None:
			right_idx = self.size - 1
		assert left_idx >= 0 and left_idx < self.size and (right_idx >= 0) and (right_idx < self.size) and (left_idx <= right_idx)
		return self.__sum(left_idx, right_idx, 0, len(self.__nodes) / 2 - 1, 1)

	def __sum(self, left_idx, right_idx, curr_left, curr_right, node_idx):
		if curr_left >= left_idx and curr_right <= right_idx:
			return self.__nodes[node_idx]
		if curr_left > right_idx or curr_right < left_idx:
			return 0
		mid = math.floor((curr_left + curr_right) / 2)
		return self.__sum(left_idx, right_idx, curr_left, mid, node_idx * 2) + self.__sum(left_idx, right_idx, mid + 1, curr_right, node_idx * 2 + 1)

def double_counts(nums):
	if len(nums) == 0:
		return []
	min_num = min(nums)
	max_num = max(nums)
	size = max(0, max_num - min_num + 2)
	counts = SegmentTree(size=size)
	result = [0] * len(nums)
	for idx in reversed(range(len(nums))):
		num = nums[idx] - min_num
		result[idx] = counts.sum(left_idx=num + 1)
		counts.update(idx=num, value=1)
	return result

def count_triplets(nums):
	doubles = double_counts(nums)
	min_num = min(nums)
	max_num = max(nums)
	size = max(0, max_num - min_num + 2)
	counts = SegmentTree(size=size)
	result = [0] * len(nums)
	for idx in reversed(range(len(nums))):
		num = nums[idx] - min_num
		result[idx] = counts.sum(left_idx=num + 1)
		counts.inc(idx=num, amount=doubles[idx])
	return result

def remove_dups(nums):
	seen = set()
	result = []
	for num in nums:
		if num not in seen:
			seen.add(num)
			result.append(num)
	return result
nums = [int(x) for x in sys.stdin.readlines()[1].split()]
doubles = double_counts(nums)
is_first_occurrence = [True] * len(nums)
seen = set()
for (idx, num) in enumerate(nums):
	if num in seen:
		is_first_occurrence[idx] = False
	seen.add(num)
min_num = min(nums)
max_num = max(nums)
size = max(0, max_num - min_num + 2)
counts = SegmentTree(size)
total = 0
for idx in reversed(range(len(nums))):
	num = nums[idx] - min_num
	if is_first_occurrence[idx]:
		total += counts.sum(left_idx=num + 1)
	counts.update(idx=num, value=doubles[idx])
print(total)


import os
import sys
from collections import defaultdict

class Fenwick:

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

	def get(self, i):
		return self.query(i) - self.query(i - 1)

	def set(self, i, v):
		cv = self.get(i)
		self.update(i, v - cv)

	def update(self, i, v):
		while i < len(self.ft):
			self.ft[i] += v
			i += i & -i

	def query(self, i):
		r = 0
		while i > 0:
			r += self.ft[i]
			i -= i & -i
		return r
n = int(input())
fa = Fenwick(n)
fb = Fenwick(n)
fc = Fenwick(n)
arr = list(map(int, input().split()))
st = defaultdict()
for i in arr:
	if i not in st:
		st[i] = 1
cn = 1
mp = defaultdict()
for i in sorted(st):
	mp[i] = cn
	cn += 1
for i in range(n):
	h = mp[arr[i]]
	fa.set(h, 1)
	fb.set(h, fa.query(h - 1))
	fc.set(h, fb.query(h - 1))
print(fc.query(n))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


import math
import os
import random
import re
import sys
n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


import math
import os
import random
import re
import sys
n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


import math
import os
import random
import re
import sys
n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


import math
import os
import random
import re
import sys
n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level * 2 + 1)]
tree_2 = [0 for i in range(last_level * 2 + 1)]
tri = [0 for i in range(100048)]

def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while index < x + last_level:
		if x < c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= c_level // 2
		c_level //= 2
	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //= 2
	while index > 0:
		tree[index] = tree[2 * index] + tree[2 * index + 1]
		index //= 2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
	sum += i
print(sum)


import math
import os
import random
import re
import sys
from collections import Counter
n = int(input())
num = sorted([(int(x), i + 1) for (i, x) in enumerate(input().split())])
m = n + 1
s = [[0] * (m + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)]
s[0][0] = 1

def Sum(s, n):
	ret = s[0]
	while n > 0:
		ret += s[n]
		n = n ^ n & ~n + 1
	return ret

def Update(s, n, v):
	while n <= m:
		s[n] += v
		n += n & ~n + 1
for (i, (n, id)) in enumerate(num):
	if i and num[i - 1][0] == num[i][0]:
		continue
	process = [(n, id)]
	if i + 1 < len(num) and num[i][0] == num[i + 1][0]:
		process.append(num[i + 1])
	for state in (3, 2, 1):
		values = []
		for (n, id) in process:
			values.append(Sum(s[state - 1], id - 1))
		if len(values) > 1:
			values[1] -= values[0]
		for (j, (n, id)) in enumerate(process):
			Update(s[state], id, values[j])
print(Sum(s[3], m - 1))