Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Hai bạn Vinh và Tú đang cùng nhau tham gia một trò chơi chọn số.

• Vinh sẽ chọn ra hai chỉ số ~d_1, d_2~ ~(1 \le d_1 < d_2 \le n)~ và ghi lại hai phần tử tương ứng.
• Tú cũng độc lập chọn ra hai chỉ số ~k_1, k_2~ ~(1 \le k_1 < k_2 \le n)~ và ghi lại hai phần tử tương ứng.
• Lưu ý: Vinh và Tú hoàn toàn có thể chọn trùng chỉ số của nhau.

Một lượt chơi được gọi là phân tầng nếu giá trị lớn nhất trong hai số Vinh chọn nhỏ hơn hẳn giá trị nhỏ nhất trong hai số Tú chọn. Nói cách khác, cách chọn các chỉ số phải thỏa mãn điều kiện:

$$\max(a_{d_1}, a_{d_2}) < \min(a_{k_1}, a_{k_2})$$

Yêu cầu: Hãy lập trình tính xem có tất cả bao nhiêu cách chọn ra bộ bốn chỉ số ~(d_1, d_2, k_1, k_2)~ tạo thành một lượt chơi phân tầng. Vì số lượng cách chọn có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên là số nguyên ~n~ ~(2 \le n \le 10^5)~.
• Dòng tiếp theo bao gồm ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

Kết quả

• In ra một số nguyên duy nhất là số lượng cách chọn thỏa mãn sau khi chia lấy dư cho ~10^9 + 7~.

Ví dụ

Input

4
1 3 2 4

Output

1

Giải thích: Cách chọn duy nhất thỏa mãn là:

• Vinh chọn cặp chỉ số ~d_1 = 1~ và ~d_2 = 3~ (tương ứng giá trị ~a_1 = 1, a_3 = 2~). Giá trị lớn nhất của Vinh là ~\max(1, 2) = 2~.
• Tú chọn cặp chỉ số ~k_1 = 2~ và ~k_2 = 4~ (tương ứng giá trị ~a_2 = 3, a_4 = 4~). Giá trị nhỏ nhất của Tú là ~\min(3, 4) = 3~.

Giới hạn

• ~2 \le n \le 10^5~.
• ~1 \le a_i \le 10^9~.

Subtask:

• 40% số test tương ứng với 40% số điểm có ~n \le 50~.
• 40% số test tương ứng với 40% số điểm có ~n \le 10^3~.
• 20% số test còn lại tương ứng với 20% số điểm còn lại không có giới hạn gì thêm.