Problem:

E: 凸凹数列

問題

  長さ $N$ の数列 $A$ が与えられる。$A$ の $i$ 項目 は $A_i$ である。
  あなたは、この数列に対して以下の操作を行うことができる。

  

    
$1 \leq i \leq N - 1$ なる整数 i を選ぶ。 $A_i$ の値と $A_{i + 1}$ の値を入れ替える。

  

  $A$ を凸凹数列にするために必要な操作の最小回数を求めよ。

  以下の条件を満たす長さ $N$ の数列を凸凹数列と定義する。
  
  

    
$1  A_i$ または $A_{i + 1}, A_{i - 1} < A_i$ を満たす。

													      直感的に言えば、 $1,\ 10,\ 2,\ 30,\ \dots (10,\ 1,\ 30,\ 2,\ \dots )$ のような、増加、減少、増加…（減少、増加、減少…）を繰り返す数列である。

													      

制約

  
入力値は全て整数である。

  
$3 \leq N \leq 10^5$

  
$i \neq j$ ならば $A_i \neq A_j$

  
$-10^9 \leq A_i \leq 10^9$

入力形式

 入力は以下の形式で与えられる。 

  $N$

  $A_1 \dots A_N$

出力

凸凹数列にするために必要な操作の最小回数を出力せよ。また、末尾に改行も出力せよ。 

サンプル

サンプル入力 1

5
1 2 3 4 5

サンプル出力 1

2

$2$ と $3$ 、 $4$ と $5$ に操作を行えば、 $1\ 3\ 2\ 5\ 4$ という凸凹数列になる。

サンプル入力 2

3
1 2 3

サンプル出力 2

1

$1$ と $2$ に操作を行う、あるいは $2$ と $3$ に操作を行うことで、凸凹数列になる。

サンプル入力 3

12
5 9 1 38 100 -23 4 16 -2 -10 -17 8

サンプル出力 3

2



Sample input:
5
1 2 3 4 5


Sample output:
2

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = n
s = 0
b = [0 for i in range(n)]
for i in range(n):
    b[i] = a[i]
for i in range(1,n):
    if i%2 == 1:
        if b[i] > b[i-1]:
            flag = True
            if i < n-1:
                if b[i-1] > b[i+1] and b[i+1] < b[i]:
                    v = b[i+1]
                    b[i+1] = b[i]
                    b[i] = v
                    flag = False
            if flag:
                v = b[i-1]
                b[i-1] = b[i]
                b[i] = v
            s += 1
    else:
        if b[i] < b[i-1]:
            flag = True
            if i < n-1:
                if b[i-1] < b[i+1] and b[i+1] > b[i]:
                    v = b[i+1]
                    b[i+1] = b[i]
                    b[i] = v
                    flag = False
            if flag:
                v = b[i-1]
                b[i-1] = b[i]
                b[i] = v
            s += 1
ans = min(ans, s)

s = 0
for i in range(n):
    b[i] = a[i]
for i in range(1,n):
    if i%2 == 0:
        if b[i] > b[i-1]:
            flag = True
            if i < n-1:
                if b[i-1] > b[i+1] and b[i+1] < b[i]:
                    v = b[i+1]
                    b[i+1] = b[i]
                    b[i] = v
                    flag = False
            if flag:
                v = b[i-1]
                b[i-1] = b[i]
                b[i] = v
            s += 1
    else:
        if b[i] < b[i-1]:
            flag = True
            if i < n-1:
                if b[i-1] < b[i+1] and b[i+1] > b[i]:
                    v = b[i+1]
                    b[i+1] = b[i]
                    b[i] = v
                    flag = False
            if flag:
                v = b[i-1]
                b[i-1] = b[i]
                b[i] = v
            s += 1
ans = min(ans, s)
print(ans)