#![allow(non_snake_case)]

use std::collections::HashSet;
use std::collections::HashMap;
use std::hash::Hash;
use proconio::{input, marker::Usize1, marker::Chars};
use itertools::Itertools;

const INF: i64 = 1 << 62;

#[derive(Debug, Clone)]
struct FenwickTree {
    n: usize,
    data: Vec<i64>,
}

impl FenwickTree {
    /// サイズ n の Fenwick Tree を作成
    fn new(n: usize) -> Self {
        let size = n + 10;
        FenwickTree {
            n: size,
            data: vec![0; size],
        }
    }

    /// p 番目に x を加算 (0-indexed)
    fn add(&mut self, mut p: usize, x: i64) {
        assert!(p < self.n);
        p += 1;
        while p < self.data.len() {
            self.data[p] += x;
            p += p & (!p + 1); // p & -p
        }
    }

    /// 区間 [0, p] の和 (0-indexed)
    fn sum(&self, mut p: usize) -> i64 {
        assert!(p < self.n);
        p += 1;
        let mut s = 0;
        while p > 0 {
            s += self.data[p];
            p &= p - 1; // p -= p & -p
        }
        s
    }

    /// 区間 [l, r] の和
    fn range_sum(&self, l: usize, r: usize) -> i64 {
        assert!(l <= r && r < self.n);
        if l == 0 {
            self.sum(r)
        } else {
            self.sum(r) - self.sum(l - 1)
        }
    }

    /// p 番目の値
    fn get(&self, p: usize) -> i64 {
        self.range_sum(p, p)
    }
}


#[derive(Debug)]
struct Compression<T> {
    vs: Vec<T>,                 // ソート済み・重複なしの値
    v2i: HashMap<T, usize>,     // 値 -> インデックス
}

impl<T> Compression<T>
where
    T: Ord + Copy + Eq + Hash,
{
    /// iterable から座標圧縮を構築
    fn new<I>(iterable: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut vs: Vec<T> = iterable.into_iter().collect();
        vs.sort();
        vs.dedup();

        let mut v2i = HashMap::new();
        for (i, &val) in vs.iter().enumerate() {
            v2i.insert(val, i);
        }

        Self { vs, v2i }
    }

    fn len(&self) -> usize {
        self.vs.len()
    }

    /// val のインデックスを返す
    fn index(&self, val: T) -> usize {
        self.v2i[&val]
    }

    /// インデックスに対応する値を返す
    fn value(&self, index: usize) -> T {
        self.vs[index]
    }

    /// iterable を圧縮後のインデックス列に変換
    fn map<I>(&self, iterable: I) -> Vec<usize>
    where
        I: IntoIterator<Item = T>,
    {
        iterable.into_iter().map(|x| self.index(x)).collect()
    }
}

fn main() {
    input! {
        N: usize,
        A: [i64; N],
    }

    let comp = Compression::new(A.iter().chain([-INF, INF].iter()));
    let xs = A.iter().map(|x| comp.index(x)).collect_vec();
    let sz = xs.len();

    let mut lt = FenwickTree::new(sz+10);
    let mut rt = FenwickTree::new(sz+10);
    let mut dup = FenwickTree::new(sz+10); // dup.get(x) : x の重複数
    for &x in &xs {
        rt.add(x, 1);
    }

    let mut ans = 0;
    for x in xs {  // 真ん中を x で固定
        // 真ん中を最小値とする
        let l = lt.range_sum(x+1, sz+5);
        let r = rt.range_sum(x+1, sz+5);
        ans += l * r; // 重複が含まれる
        ans -= dup.range_sum(x+1, sz+5); // 重複を除く

        // 真ん中を最大値とする
        let l = lt.sum(x-1);
        let r = rt.sum(x-1);
        ans += l * r; // 重複が含まれる
        ans -= dup.sum(x-1); // 重複を除く

        lt.add(x, 1);
        rt.add(x, -1);
        let old = dup.get(x);
        dup.add(x, lt.get(x) * rt.get(x) - old);
    }

    println!("{}", ans);
}