Cho dãy số \(A\) gồm \(N\) phần tử \(a_{1}, a_{2}, \ldots, a_{N}\). Hãy đếm số cặp \(L, R\) \((1 \leq L \leq R \leq N)\) sao cho:

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \leq 3 \times 10^{5})\) mô tả số lượng phần tử của dãy số \(A\);
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_{i}\) \((a_{i} \leq 10^{9}; 1 \leq i \leq N)\) mô tả các phần tử của dãy số \(A\).

Output

• In ra một số nguyên là số cặp thoả mãn yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): dãy số tăng dần: \(a_{i} \leq a_{i + 1}\) \((1 \leq i \leq N)\).
• Subtask \(3\) (\(20\%\) số điểm): không có rằng buộc gì thêm.

Example

3
2 2 4

4