class Treap
attr_reader :size
def initialize(*values)
@tree, @size = nil, 0
values.flatten.uniq.each{|v| self.add(v)}
end
def add(value)
@tree = insert(@tree, Node.new(value))
@size += 1
self
end
def root
@tree
end
def include?(value)
node = @tree
while node
if node.key > value
node = node.left
elsif node.key < value
node = node.right
else
return true
end
end
false
end
#find the key which > value
def find_more_than(value)
ret = nil
node = @tree
while node
if node.key > value
ret = node.key
node = node.left
else
node = node.right
end
end
ret
end
#find the key which >= value
def find_no_less_than(value)
ret = nil
node = @tree
while node
if node.key >= value
ret = node.key
node = node.left
else
node = node.right
end
end
ret
end
#find the key which < value
def find_less_than(value)
ret = nil
node = @tree
while node
if node.key < value
ret = node.key
node = node.right
else
node = node.left
end
end
ret
end
#find the key which <= value
def find_no_more_than(value)
ret = nil
node = @tree
while node
if node.key <= value
ret = node.key
node = node.right
else
node = node.left
end
end
ret
end
def to_s
@tree.to_s
end
def [](value)
node = @tree
while node
if node.key > value
node = node.left
elsif node.key < value
node = node.right
else
return node
end
end
nil
end
def clear
@tree = nil
@size = 0
self
end
def delete(value)
old, @tree = remove(@tree, value)
old
end
def each(order = :ascending)
stack = []
node = @tree
build_order = (order == :ascending) ? :left : :right
stack_order = (order == :ascending) ? :right : :left
while node
stack << node
node = node.send(build_order)
end
until stack.empty?
node = stack.last
if node.send(stack_order) == nil
tmp = stack.pop
while !stack.empty? and stack.last.send(stack_order) == tmp
tmp = stack.pop
end
else
tmp = node.send(stack_order)
while tmp
stack << tmp
tmp = tmp.send(build_order)
end
end
yield node
end
end
def height
@tree ? @tree.height : 0
end
alias :=== :include?
alias :> :find_more_than
alias :>= :find_no_less_than
alias :< :find_less_than
alias :<= :find_no_more_than
alias :<< :add
private
def insert(tree, node)
return node if tree == nil
if node.key < tree.key
tree.left = insert(tree.left, node)
tree = tree.rotate_right if tree.priority > tree.left.priority
elsif node.key > tree.key
tree.right = insert(tree.right, node)
tree = tree.rotate_left if tree.priority > tree.right.priority
else
@size -= 1
end
tree
end
def remove(tree, value)
return [nil, nil] if tree == nil
old = nil
if value < tree.key
old, tree.left = remove(tree.left, value)
elsif value > tree.key
old, tree.right = remove(tree.right, value)
else
old = tree.key
tree = tree.pop_root
@size -= 1
end
[old, tree]
end
def generate_priority
rand(INT_MAX)
end
end
class Node
attr_accessor :key, :left, :right
attr_reader :priority
INT_MAX = 2 ** (1.size * 8)
def initialize(key)
@key, @priority = key, rand(INT_MAX)
@right, @left = nil, nil
end
def rotate_right
tmp, @left, tmp.right = @left, @left.right, self
tmp
end
def rotate_left
tmp, @right, tmp.left = @right, @right.left, self
tmp
end
def pop_root
return @right if @left == nil
return @left if @right == nil
tmp = nil
if @left.priority >= @right.priority
tmp = rotate_left
tmp.left = pop_root
else
tmp = rotate_right
tmp.right = pop_root
end
tmp
end
def height
r_height = @right ? @right.height : 0
l_height = @left ? @left.height : 0
[r_height, l_height].max + 1
end
def to_s
print
end
def print(level = 0)
desc = ""
desc << "#{@left.print(level + 1)}-" unless @left.nil?
desc << "#" * level
desc << "[#{@key}, #{@priority}]"
desc << "-#{@right.print(level + 1)}" unless @right.nil?
desc
end
end
n = gets.to_i
treap = Treap.new([-1, n])
b = Array.new(n)
gets.split.map(&:to_i).each_with_index{|v, idx|b[v - 1] = idx}
ans = 0
0.upto(n - 1){|idx|
v = b[idx]
cv = (treap.> v) - v
j = treap.< v
ans += idx * cv * (v - j)
treap << v
}
puts ans + n*(n+1)/2