#include <iostream>
enum Colour {
Red = 0,
Black = 1
};
class Node {
public:
int value;
Colour colour = Red;
int num_left = 0;
int num_right = 0;
int num_bigger = 0;
Node * parent = NULL;
Node * left = NULL;
Node * right = NULL;
public:
Node(int val) : value(val) { }
Node(int val, Node * NIL) : value(val), parent(NIL), left(NIL), right(NIL) { }
};
class RB_TREE {
private:
Node * root;
Node * NIL;
int cnt = 0;
public:
RB_TREE();
void Insert(int val);
void Insert_Fix(Node * node);
void Left_Rotate(Node * node);
void Right_Rotate(Node * node);
int getCount() { return cnt; }
};
RB_TREE::RB_TREE() {
NIL = new Node(-1);
NIL->colour = Black;
root = NIL;
}
void RB_TREE::Insert(int val) {
Node * node = new Node(val, NIL);
Node * pos = NIL;
Node * current = root;
//std::cout << "--- Node: " << val << " ---\n"; //temp
while(current != NIL) {
pos = current;
//std::cout << "pos: " << pos->value << '\n'; //temp
if(node->value < current->value) {
current->num_left++;
current = current->left;
if(current !=NIL) {
//std::cout << "[LEFT]Node " << current->value
// << "'s num_bigger Before: " << current->num_bigger << " -> "; //temp
current->num_bigger =
current->parent->num_bigger + current->num_right + 1;
//std::cout << "After: " << current->num_bigger << '\n'; //temp
}
}
else {
if(current->right != NIL) {
//std::cout << "{RIGHT}Node " << current->right->value
// << "'s num_bigger Before: " << current->right->num_bigger << " -> "; // temp
current->right->num_bigger = current->num_bigger - current->right->num_left - 1;
//std::cout << "After: " << current->right->num_bigger << '\n'; //temp
}
//std::cout << "[RIGHT]Node " << current->value
// << "'s num_bigger Before: " << current->num_bigger << " -> "; // temp
current->num_bigger++;
current->num_right++;
//std::cout << "After: " << current->num_bigger << '\n'; //temp
current = current->right;
}
}
node->parent = pos;
if(pos == NIL) {
root = node;
}
else if(node->value < pos->value) {
pos->left = node;
node->num_bigger = pos->num_bigger + 1;
}
else {
pos->right = node;
node->num_bigger = pos->num_bigger - 1;
}
cnt += node->num_bigger;
//std::cout << "Final num_bigger: " << node->num_bigger << '\n'; // temp
Insert_Fix(node);
}
void RB_TREE::Insert_Fix(Node * node) {
while(node->parent->colour == Red) {
if(node->parent == node->parent->parent->left) {
Node * uncle = node->parent->parent->right;
if(uncle->colour == Red) {
node->parent->colour = Black;
uncle->colour = Black;
node->parent->parent->colour = Red;
node = node->parent->parent;
}
else{
if(node == node->parent->right) {
node = node->parent;
Left_Rotate(node);
}
node->parent->colour = Black;
node->parent->parent->colour = Red;
Right_Rotate(node->parent->parent);
}
}
else {
Node * uncle = node->parent->parent->left;
if(uncle->colour == Red) {
node->parent->colour = Black;
uncle->colour = Black;
node->parent->parent->colour = Red;
node = node->parent->parent;
}
else{
if(node == node->parent->left) {
node = node->parent;
Right_Rotate(node);
}
node->parent->colour = Black;
node->parent->parent->colour = Red;
Left_Rotate(node->parent->parent);
}
}
}
root->colour = Black;
}
void RB_TREE::Left_Rotate(Node * node) {
Node * other = node->right;
node->right = other->left;
node->num_right -= other->num_right + 1;
other->num_left += node->num_left + 1;
if(other->left != NIL) {
other->left->parent = node;
}
other->parent = node->parent;
if(node->parent == NIL) {
root = other;
}
else if(node == node->parent->left) {
node->parent->left = other;
}
else {
node->parent->right = other;
}
other->left = node;
node->parent = other;
}
void RB_TREE::Right_Rotate(Node * node) {
Node * other = node->left;
node->left = other->right;
node->num_left -= other->num_left + 1;
other->num_right += other->num_right + 1;
if(other->right != NIL) {
other->right->parent = node;
}
other->parent = node->parent;
if(node->parent == NIL) {
root = other;
}
else if(node == node->parent->right) {
node->parent->right = other;
}
else {
node->parent->left = other;
}
other->right = node;
node->parent = other;
}
int main() {
RB_TREE rbt;
int num, val;
std::cin >> num;
for(int i = 0; i < num; i++) {
std::cin >> val;
rbt.Insert(val);
}
std::cout << rbt.getCount() << '\n';
return 0;
}