← 返回题目列表

Codeforces · 653/C

C. 熊和上下

中文机器翻译题面 查看原题

生活起起落落,就像精彩的序列一样。如果满足以下两个条件,则序列 t1, t2, ..., tn 被称为“nice”:

- 对于每个奇数 i < n,ti < ti + 1;
- 对于每个偶数 i < n,ti > ti + 1。

例如,序列 (2, 8)、(1, 5, 1) 和 (2, 5, 1, 100, 99, 120) 很好,而 (1, 1)、(1, 2, 3) 和 (2, 5, 3, 2) 则不好。

Bear Limak 有一个正整数序列 t1, t2, ..., tn。这个序列现在不太好,Limak 希望通过一次交换来修复它。他将选择两个索引 i < j 并交换元素 ti 和 tj 以获得一个好的序列。数一下有多少种方法可以做到这一点。如果为交换选择的元素索引不同,则两种方式被认为是不同的。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 150 000) - 序列的长度。

第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 150 000) — 初始序列。保证给定的序列不好。

输出

打印一次交换两个元素以获得良好序列的方法数。

示例

输入 #1

5
2 8 4 7 7

输出 #1

2

输入 #2

4
200 150 100 50

输出 #2

1

输入 #3

10
3 2 1 4 1 4 1 4 1 4

输出 #3

8

输入#4

9
1 2 3 4 5 6 7 8 9

输出#4

0

注意

在第一个示例中,有两种方法可以通过一次交换获得良好的序列:

1. 将 t2 = 8 与 t4 = 7 交换。
2. 将 t1 = 2 与 t5 = 7 交换。

在第二个示例中,只有一种方法 — Limak 应该将 t1 = 200 替换为 t4 = 50。