Trong một dãy \(x_1, x_2, \ldots, 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.

Bạn được cho một dãy \(a_1, a_2, \ldots, 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 là dãy đẹp.

Input

• Dòng đầu tiên gồm một số nguyên dương \(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, \ldots, 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

• \(30\%\) số điểm có \(n \le 20\).
• \(30\%\) số điểm khác có \(a_i \le 2\).
• \(20\%\) số điểm khác có \(n \le 2000\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Example

4
1 3 2 4

3