Trong một dãy ~x_1,x_2,\dots,x_k~, số ~x_i~ được gọi là cực trị địa phương khi và chỉ khi ~x_{i-1}<x\_i>x_{i+1}~ hoặc ~x_{i-1}>x_i<x_{i+1}~. Một dãy ~x~ được gọi là đẹp khi và chỉ khi dãy tồn tại ít nhất một cực trị địa phương.</p>

Bạn được cho một dãy ~a_1,a_2,\dots,a_n~. Hãy đếm số lượng dãy con (không nhất thiết liên tiếp) của dãy ~a~ là dãy đẹp.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(3 \le n \le 2 \cdot 10^5)~.

• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9)~.

Output

Một dòng duy nhất gồm số lượng dãy con của ~a~ là dãy đẹp. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho ~10^9+7~.

Scoring

Sample Input 1

4
1 3 2 4

Sample Output 1

3

Notes

Dãy ~(1,3,2)~ là dãy đẹp vì có cực trị địa phương tại ~x_2=3~.

Dãy ~(3,2,4)~ là dãy đẹp vì có cực trị địa phương tại ~x_3=2~.

Dãy ~(1,3,2,4)~ là dãy đẹp vì có cực trị địa phương tại ~x_2~ và ~x_3~.