Giải bài trực tuyến

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é.

Giới hạn

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

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.

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:

7
3 5 2 7 6 1 4

Output:

2

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