use std::io;

pub trait ExRead {
    fn read_line(&mut self) -> io::Result<String>;
    fn read_to_string(&mut self) -> io::Result<String>;
}

impl ExRead for io::StdinLock<'_> {
    fn read_line(&mut self) -> io::Result<String> {
        let mut buf = String::new();
        io::BufRead::read_line(self, &mut buf).map(|_| buf)
    }

    fn read_to_string(&mut self) -> io::Result<String> {
        self.read_line().map(|s| s.trim().to_string())
    }
}

pub trait SplitAndParse<T: std::str::FromStr> {
    type Result;
    fn split_and_parse(self) -> Self::Result;
}

impl<'a, T: std::str::FromStr> SplitAndParse<T> for &'a str {
    type Result = Result<Vec<T>, <T as std::str::FromStr>::Err>;
    fn split_and_parse(self) -> Self::Result {
        self.split_whitespace()
            .map(|e| e.parse())
            .fold(Ok(Vec::new()),
                |acc, e| acc.and_then(|mut v| e.map(|parsed| {v.push(parsed); v})))
    }
}

extern crate num;

pub fn abs_diff<T: num::Num + Copy + Ord>(n1: T, n2: T) -> T {
    std::cmp::max(n1, n2) - std::cmp::min(n1, n2)
}

fn main() {
    let n: usize;
    let mut a: Vec<(usize, usize)>;

    {
        let stdin = std::io::stdin();
        let mut lkin = stdin.lock();
        let mut input = lkin.read_line().unwrap().split_and_parse().unwrap().into_iter();
        n = input.next().unwrap();
        a = (1..=n).zip(lkin.read_line().unwrap().split_and_parse().unwrap()).collect();
    }

    a.sort_by_key(|&(_, a)| a);
    let mut dp = Vec::new();
    dp.resize(n+1, Vec::new());
    dp.iter_mut().enumerate().for_each(|(i, v)| v.resize(n-i+1, 0));
    for i in 1..=n {
        dp[i][0] = dp[i-1][0] + a[n-i].1 * abs_diff(a[n-i].0, i);
        dp[0][i] = dp[0][i-1] + a[n-i].1 * abs_diff(a[n-i].0, i);
    }

    for pick in 2..=n {
        for r_align in 1..pick {
            dp[pick - r_align][r_align] = std::cmp::max(
                dp[pick - r_align - 1][r_align] + a[n-pick].1 * abs_diff(a[n-pick].0, pick - r_align),
                dp[pick - r_align][r_align - 1] + a[n-pick].1 * abs_diff(a[n-pick].0, n - r_align + 1)
            );
        }
    }
  
    println!("{}", dp.iter().max_by_key(|v| v.last().unwrap()).unwrap().last().unwrap());
}
