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.