The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of n vertices. Each vertex i has its own value a_i. All vertices are connected in series by edges. Formally, for every 1 ≤ i < n there is an edge between the vertices of i and i+1.

Denote the function f(l, r), which takes two integers l and r (l ≤ r):

  * We leave in the tree only vertices whose values ​​range from l to r. 
  * The value of the function will be the number of connected components in the new graph. 



Your task is to calculate the following sum: $$$∑_{l=1}^{n} ∑_{r=l}^{n} f(l, r) $$$

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the values of the vertices.

Output

Print one number — the answer to the problem.

Examples

Input


3
2 1 3


Output


7

Input


4
2 1 1 3


Output


11

Input


10
1 5 2 5 5 3 10 6 5 1


Output


104

Note

In the first example, the function values ​​will be as follows: 

  * f(1, 1)=1 (there is only a vertex with the number 2, which forms one component) 
  * f(1, 2)=1 (there are vertices 1 and 2 that form one component) 
  * f(1, 3)=1 (all vertices remain, one component is obtained) 
  * f(2, 2)=1 (only vertex number 1) 
  * f(2, 3)=2 (there are vertices 1 and 3 that form two components) 
  * f(3, 3)=1 (only vertex 3) 

Totally out 7.

In the second example, the function values ​​will be as follows: 

  * f(1, 1)=1 
  * f(1, 2)=1 
  * f(1, 3)=1 
  * f(1, 4)=1 
  * f(2, 2)=1 
  * f(2, 3)=2 
  * f(2, 4)=2 
  * f(3, 3)=1 
  * f(3, 4)=1 
  * f(4, 4)=0 (there is no vertex left, so the number of components is 0) 

Totally out 11.
import java.util.*;
import java.math.*;

// **** C. Problem for Nazar ****

public class C {
	static char [] in = new char [100000];
	static long MOD = 1000000007L;
	static long modinv2 = BigInteger.valueOf(2).modInverse(BigInteger.valueOf(MOD)).longValue();
	public static void main (String [] arg) throws Throwable {
		long l = nextLong();
		long r = nextLong();
		long ans = sumto(r) - sumto(l-1);
		while (ans < 0) ans += MOD;
		System.out.println(ans % MOD);
	}
	public static long sumto(long n) {
		if (n == 0) return 0;
		if (n == 1) return 1;
		long cur_pos = 2;
		int parity = 0;
		long pow2 = 2;
		long cur_odd = 3;
		long cur_even = 2;
		
		while (n >= (cur_pos + pow2)) {
			long pow2m = pow2 % MOD;
			if (parity == 1) {
				cur_odd = (cur_odd + (pow2) * 2);
			} else {
				cur_even = (cur_even + (pow2) * 2);
			}
			parity = 1-parity;
			cur_pos += pow2;
			pow2 = (pow2<<1);
			//System.err.println(cur_odd + " - " + cur_even);
		}
		long remains = (n - cur_pos + 1) % MOD;
		long rangeans = (parity == 1) ? 
			(sumtogauss(2*remains) + 2*remains*(cur_odd-1)) % MOD:
			(sumtogauss(2*remains) + 2*remains*(cur_even-1)) % MOD;
		rangeans = (rangeans - remains + MOD) % MOD;
		rangeans = (rangeans * modinv2) % MOD;
		
		long skipans1 = sumskip( (parity == 1) ? cur_even-2 : cur_odd - 2 , 1-parity);
		long skipans2 = sumskip( (parity == 1) ? cur_odd-2 : cur_even - 2 , parity);
		//System.err.println(skipans1 + " , " + skipans2 + " , " + rangeans);
		long ans = rangeans + skipans1 + skipans2;
		while (ans < 0) ans += MOD;
		return (ans) % MOD;
	
	}
	public static long sumskip(long f, int parity) {
		long gsum = sumtogauss(f + parity);
		long num = (f+parity) >> 1;
		long ans = (gsum - num + MOD) % MOD;
		if (parity == 1) {
			return (ans * modinv2) % MOD;
		} else {
			return (((ans * modinv2) % MOD) + num) % MOD;
		}
	}
	public static long sumtogauss(long f) {
		f = f % MOD;
		return (((f * (f+1)) % MOD) * modinv2) % MOD;
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 45) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 40 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 40) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
	public static int[] sieve(int LIM) {
		int i,count = 0;
		boolean [] b = new boolean [LIM];
		for (i = 2;i<LIM; ++i) if (!b[i]) {count++; for (int j = i<<1; j<LIM; j+=i) b[j] = true;}
		int [] primes = new int[count];
		for (i = 2,count=0;i<LIM;++i) if (!b[i]) primes[count++] = i;
		return primes;
	}
	public static int[] numPrimeFactors(int LIM) {
		int i,count = 0;
		int [] b = new int [LIM];
		for (i = 2;i<LIM; ++i) if (b[i] == 0) {count++; for (int j = i; j<LIM; j+=i) b[j]++;}
		return b;
	}
}

/* Full Problem Text:
  
Nazar, a student of the scientific lyceum of the Kingdom of Kremland, is known for his outstanding mathematical abilities.
Today a math teacher gave him a very difficult task.
Consider two infinite sets of numbers.
The first set consists of odd positive numbers (1, 3, 5, 7, ...),
and the second set consists of even positive numbers (2, 4, 6, 8, ...).
At the first stage, the teacher writes the first number on the endless blackboard from the first set, in the second stage the first two numbers from the second set, on the third stage the next four numbers from the first set, on the fourth the next eight numbers from the second set and so on.
In other words, at each stage, starting from the second, he writes out two times more numbers than at the previous one, and also changes the set from which these numbers are written out to another.
The ten first written numbers: 1, 2, 4, 3, 5, 7, 9, 6, 8, 10.
Let's number the numbers written, starting with one.
The task is to find the sum of numbers with numbers from l to r for given integers l and r.
The answer may be big, so you need to find the remainder of the division by 1000000007 (10^9+7).
Nazar thought about this problem for a long time, but didn't come up with a solution.
Help him solve this problem.

 */