Pirate bị mê hoặc bởi vẻ đẹp lộng lẫy của những đôi cánh bướm. Chàng đi khắp nơi, sưu tầm những loài bướm lộng lẫy nhất, quý hiếm nhất để đem về nuôi trong khu vườn bí mật (Secret Garden) của mình. Hằng ngày, đôi mắt của Pirate không thể nào rời khỏi những đôi cánh lập lờ giữa không trung ấy.

Nhờ ngắm bướm thường xuyên nên Pirate có thêm nhiều cảm hứng hội họa. Pirate muốn vẽ bướm thật sống động để xứng đáng với vẻ đẹp của chúng nhưng không biết làm thế nào. Một ngày nọ, khi đang nghiên cứu về một bộ tứ (~i~, ~j~, ~p~, ~q~) (~i < j < p < q~, lưu ý là các số này là chỉ số của các phần tử) của một hoán vị { ~a_{i}~ } của các số từ ~1~ đến ~N~, chàng bỗng nhận ra rằng chỉ cần đặt các điểm thể hiện ~i~, ~j~, ~p~, ~q~, trên một đường thẳng, theo thứ tự xuất hiện của chúng trong dãy số (từ trái sang phải), rồi lại kẻ một đường thẳng khác song song, và hoán vị bộ tứ theo thứ tự tăng dần của các số tương ứng với chúng trong dãy số (tức là các số ~a_{i}~, ~a_{j}~, ~a_{p}~, ~a_{q}~), thì khi nối các điểm tương ứng với nhau thì có thể vẽ được phác thảo của một chú bướm. Sau một thời gian tìm tòi, Pirate nhận ra rằng nếu bộ tứ thỏa mãn ~a_{j} < a_{q} < a_{i} < a_{p}~ thì sẽ phác thảo sẽ có hình dạng đẹp nhất (như các bạn thấy trong hình, từ phác thảo Pirate đã vẽ đựơc một tuyệt tác hồ điệp phải không nào).

Với mỗi bộ tứ như vậy Pirate sẽ vẽ được một chú bướm cho mình. Các bạn giúp Pirate đếm xem chàng sẽ vẽ được bao nhiêu bướm nhé.

Input

• Dòng ~1~ chứa số nguyên ~N~.
• Dòng ~2~ chứa ~N~ số là một dãy hoán vị từ ~1~ đến ~N~.

Output

• Một số nguyên duy nhất là kết quả tìm được.

Giới hạn

• Trong 30% test đầu tiên, ~N \leq 200~
• Trong 40% test tiếp theo, ~N \leq 3000~
• Trong 30% test còn lại, ~N \leq 10\,000~

Sample Input

7
3 5 2 7 6 1 4

Sample Output

2

Note

Giải thích: Hai bộ tứ thỏa mãn là (2, 3, 4, 7) và (2, 3, 5, 7).