#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <map>#include <string>#include <queue>using namespace std;#define SZ(v) ((int)(v).size())#define REP(i, n) for (int i = 0; i < (n); ++i) const int maxint = -1u>>1;const int maxn = 30 + 3;int n, ans;vector<int> a;pair<int, int> f[maxn];int d[maxn], u[maxn];int up(const vector<int> &a, int t) { int n = a.size(); for (int i = 0; i < n; ++i) { f[i] = make_pair(1, -1); for (int j = 0; j < i; ++j) { if (a[j] * t <= a[i] * t) { if (f[i].first < f[j].first + 1 || f[i].first == f[j].first + 1 && a[f[i].second] * t <= a[j] * t) { f[i] = make_pair(f[j].first + 1, j); } } } } int x = 0; for (int i = 0; i < n; ++i) { if (f[x].first < f[i].first || f[x].first == f[i].first && a[i] * t >= a[x] * t) x = i; } return f[x].first;}void dfs(int dep, int cnt1, int cnt2) { if (cnt1 + cnt2 >= ans) return ; if (dep == n) { ans = cnt1 + cnt2; return; } for (int i = 0; i <= cnt1; ++i) { if (u[i] > a[dep]) continue; int c = u[i]; u[i] = a[dep]; dfs(dep + 1, cnt1 + (i == cnt1), cnt2); u[i] = c; } for (int i = 0; i <= cnt2; ++i) { if (d[i] < a[dep]) continue; int c = d[i]; d[i] = a[dep]; dfs(dep + 1, cnt1, cnt2 + (i == cnt2)); d[i] = c; }}bool sb(const vector<int> &a) { if (n == 1) return true; if (n != 3) return false; return ((a[0] - a[1]) * (a[2] - a[1]) > 0);}int main() { while (scanf("%d", &n) == 1 && n) { a.clear(); for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); a.push_back(x); } if (sb(a)) { printf("0n"); continue; } ans = min(up(a, 1), up(a, -1)); memset(u, 0, sizeof(u)); memset(d, 100, sizeof(d)); dfs(0, 0, 0); printf("%dn", ans); } return 0;}
