题目背景

收藏家大卫.戴有一排古董瓶，每个古董瓶都有自己的高度。随着收藏的古董瓶越来越多，陈列柜显得很拥挤。大卫决定把这排中的一部分古董瓶移走，将剩下的留在原地，使得剩下的古董瓶有足够空间展示，同时，大卫希望剩下的古董瓶排列得比较别致。

题目描述

具体而言，这些古董瓶的高度可以看成一列整数 $h_1,h_2,...,h_n（0≤h_i≤ 10^9）$。设当一部分古董瓶被移走后，剩下的古董瓶的高度依次为 $g_1,g_2,...,g_m$。大卫希望下面两个条件中至少有一个满足：

条件一：对于所有整数$i$， $g_{2i}>g_{2i-1}$，且$g_{2i} > g_{2i+1}$；

条件二：对于所有整数$i$， $g_{2i}<g_{2i-1}$，且$g_{2i} < g_{2i+1}$。

注意上面两个条件在 $m=1$ 时同时满足，当 $m>1$ 时最多有一个能满足。

请你帮大卫算出他最多能将多少个古董瓶留在原地。

输入

第一行包含一个整数 $n（1≤n≤2×10^6）$，表示开始时古董瓶的个数。

第二行包含 $n$ 个整数，依次为 $h_1,h_2,...,h_n$ ,表示每个古董瓶的高度。

输出

输出一行，包含一个整数，表示最多能留在原地的古董瓶的个数。

样例

5
5 3 2 1 2

3

样例解释

有多种方法可以正好保留 $3$ 个古董瓶，例如，留下第 $1、4、5$ 个，高度分别为 $5、1、2$，满足条件二。