shil-and-wave-seqeuncemonk_16095
Given a sequence A1 , A2 , A3 .. AN of length N . Find total number of wave subsequences  having length greater than 1.
Wave subsequence of sequence A1 , A2 , A3 .. AN is defined as a set of integers i1 , i2 .. ik such that Ai1 < Ai2 > Ai3  < Ai4 .... or Ai1 > Ai2 < Ai3  > Ai4 ....    and  i1 < i2 < ...<  ik.Two subsequences i1 , i2 .. ik  and j1 , j2 .. jm  are considered different if k != m or there exists some index l such that il ! = jl

INPUT:
First line of input consists of integer N denoting total length of sequence.Next line consists of N integers A1 , A2 , A3 .. AN .

OUTPUT:
Output total number of wave subsequences of given sequence . Since answer can be large, output it modulo 10^9+7

CONSTRAINTS:
1 ≤ N ≤ 10^5 
1 ≤ Ai ≤ 10^5

SAMPLE INPUT
5
1 3 5 4 2

SAMPLE OUTPUT
17

Explanation

All the possible sequences are: [ 1 3 ] , [1 5 ] , [ 1 4 ] , [1 2 ]  , [1 3 2] , [1 4 2 ] , [1 5 2] , [1 5 4] , [3 5] , [3 4] , [3 2] , [3 5 2] , [3 4 2] , [3 5 4] , [5 4] , [5 2 ] , [4 2] . Note that value in the bracket are the values from the original sequence whose positions are maintained.
def readLine(func):
    return [func(v) for v in raw_input().strip().split(' ')]

(n) = readLine(int)
arr = readLine(int)
MAX = 100001
MOD = 10**9+7
constTree = [0] * (MAX)
lowTree = [0] * (MAX)
highTree = [0] * MAX


def update(tree, num, val):
    while num < MAX:
        tree[num] += val
        tree[num]%=MOD
        num += (num) & (-num)


def query(tree, num):
    ans = 0
    while num > 0:
        ans += tree[num]
        ans%=MOD
        num -= num & (-num)
    return ans


def queryLower(num):
    return query(constTree, num - 1) + query(lowTree, num - 1)


def queryHigher(num):
    return query(constTree, MAX - 1) - query(constTree, num) + query(highTree, MAX - 1) - query(highTree, num)  

# print arr

sm= 0

for el in arr:
    (l, h) = (queryLower(el), queryHigher(el))
    sm+=l+h
    sm%=MOD
    # print el, 'lower: ', l, 'higher: ', h
    update(constTree, el, 1)
    update(lowTree, el, h)
    update(highTree, el, l)

print sm