给定一个正整数序列 a1,a2,…,an(1≤n≤105,1≤ai≤109)a_1,a_2,\dots, a_n(1\le n\le10^5,1\le a_i\le10^9)a1,a2,…,an(1≤n≤105,1≤ai≤109)。
进行一次操作是选定两个整数 i,b(1≤i≤n,∣b∣≤2×109)i,b(1\le i\le n,|b|\le 2\times10^9)i,b(1≤i≤n,∣b∣≤2×109) 让 ai=ba_i=bai=b。
求最少使用几次上面的操作使得序列 aaa 满足存在正整数 1≤k≤n1\le k\le n1≤k≤n 并且 ∀1≤i≤k−1,ai<ai+1\forall1\le i\le k-1,a_i<a_{i+1}∀1≤i≤k−1,ai<ai+1 且 ∀k+1≤i≤n,ai−1>ai\forall k+1\le i \le n,a_{i-1}>a_i∀k+1≤i≤n,ai−1>ai。
输入共两行。
第一行一个正整数 nnn。
第二行 nnn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an。
输出共一行一个整数，为最少的操作次数。
9 1 1 2 2 3 2 2 1 1
5
对于 100%100\%100% 的数据，1≤n≤105,1≤ai≤109,∣b∣≤2×1091 \le n \le 10 ^5,1\le a_i\le10^9,|b|\le 2\times10^91≤n≤105,1≤ai≤109,∣b∣≤2×109。