Mèo ~Capoo~ rất thích làm việc với mảng và những con số. Do dó, trong ngày sinh nhật sắp tới của mèo ~Capoo~, mọi người đã chuẩn bị một dãy số ~a_1, a_2, a_3, ..., a_n~.
Mèo ~Capoo~ không thích các cặp số nghịch thế xuất hiện trong dãy số. Vì thế, để làm cho mèo ~Capoo~ cảm thấy hạnh phúc trong ngày sinh nhật thì cần giảm số cặp nghịch thế xuống mức tối thiểu bằng cách nhân một số phần tử trong dãy cho ~-1~ hoặc giữ nguyên dãy ban đầu. Vì thời gian gấp rút nên các bạn mèo của ~Capoo~ cần sự hỗ trợ, bạn hãy giúp các bạn mèo giải quyết vấn đề này nhé!
Một nghịch thế trong dãy ~a_1, a_2, a_3, ..., a_n~ là một cặp số ~i, j~ ~(1 \le i \lt j \le n)~ sao cho ~a_i \gt a_j~.
Dữ liệu vào
- Dòng thứ nhất chứa số nguyên dương ~n~ ~(n \le 10^5)~.
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, ..., a_n~ ~(|a_i| \le 10^5)~.
Dữ liệu ra
In ra màn hình số cặp nghịch thế tối thiểu có trong dãy.
Ràng buộc
Subtask ~1~ ~(30\%)~: ~1 \le n \le 15~.
Subtask ~2~ ~(30\%)~: ~15 \le n \le 5000~.
Subtask ~3~ ~(40\%)~: ~5000 \le n \le 100000~.
Ví dụ 1
Dữ liệu
3
-8 7 2
Kết quả
0
Giải thích
Dãy số có thể viết lại thành: -8 -7 2
Ví dụ 2
Dữ liệu
6
16 -24 -64 8 48 48
Kết quả
3
Giải thích
Dãy số có thể giữ nguyên.
Comments
Dạ bài này có trên codeforces không ạ. Nếu có cho em xin nguồn với ạ
E. Jeff and Permutation nhé bạn