| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P161SUMC - ROUND 1C - Cầu toàn |
Ryze rất thích chơi với những dãy số. Nhân ngày sinh nhật của mình, anh được Teemo tặng cho 1 dãy số gồm n phần tử: p1, p2, ..., pn.
Nhưng Ryze là một người cầu toàn, và anh không thích trong dãy số của mình có nhiều cặp số nghịch thế. Một cặp nghịch thế trong 1 dãy số a1, a2, ..., an là cặp phần tử có chỉ số i, j (1 <= i < j <= n) thỏa mãn ai > aj.
Teemo muốn lấy lòng Ryze và không hề muốn anh ta nổi giận, nên Teemo phải cố gắng làm cho dãy p của mình có ít cặp nghịch thế nhất có thể. Biết rằng Teemo chỉ có thể thay đổi giá trị của các phần tử trong dãy bằng cách nhân nó với -1, và Teemo tuyệt đối không được phép đổi chỗ các phẩn tử trong dãy.
Bạn hãy giúp Teemo tìm xem số cặp nghịch thế nhỏ nhất có thể là bao nhiêu.
Input
Dòng đầu tiên gồm số nguyên n (1 <= n <= 2000).
Dòng tiếp theo gồm n số nguyên là phần tử của dãy p1, p2, ..., pn. (|pi| ≤ 105). Các số phân cách nhau bởi dấu cách.
Output
In ra kết quả bài toán – là số cặp nghịch thế nhỏ nhất của dãy p mà Teemo có thể xây dựng được.
Example
Test 1:
Input:
2
2 1
Output:
0
Test 2:
Input:
9
-2 0 -1 0 -1 2 1 0 -1
Output:
6
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-07 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
