Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMFOUR - Secret Garden

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmfour


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ị {ai} 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ố ai, aj, ap, aq), 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 aj < aq < ai < ap 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).

Được gửi lên bởi:VOJ Team
Ngày:2013-06-27
Thời gian chạy:4s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC

hide comments
2017-12-18 18:11:54


Last edit: 2017-12-19 04:27:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.