题目描述

设有两个数 $x,y$，且顺序为 $x,y$。如果对它们执行一次卷积操作，会得到两个数 $-y,-x$，顺序也是 $-y,-x$。也就是说：交换这两个数的位置，并把它们都变成相反数。

现在把这个操作推广到数组上。给定一个长度为 $N$ 的整数数组 $a$，你可以任意多次选择两个相邻元素，对它们执行上述卷积操作。

你的任务是判断能否通过若干次操作，使数组变成非降序。如果可以，求达到某个非降序数组所需的最少操作次数。

请编写程序 convolution 完成这个任务。

输入格式

第一行输入一个正整数 $N$，表示数组长度。

第二行输入 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示初始数组。

输出格式

输出一个整数：

• 若无法变成非降序数组，输出 -1；
• 否则输出一个非负整数，表示最少需要的卷积操作次数。

数据范围

• $1 \le N \le 5\times 10^5$；
• $-10^9 \le a_i \le 10^9$。

子任务

一个子任务的分数仅在通过该子任务的全部测试点以及它依赖的子任务后获得。

样例 1

输入

6
-2 7 -1 -8 2 8

输出

3

样例解释

一种最优操作过程为：

-2 7 -1 -8 2 8
=> -2 1 -7 -8 2 8
=> -2 1 -7 -2 8 8
=> -2 1 2 7 8 8

不存在少于 3 次操作的方案。

样例 2

输入

4
1 -1 1 -1

输出

-1

样例解释

无法变成非降序数组。