1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//Andrzej Jabłoński
#include "bits/stdc++.h"
#define forx(i,b,e) for(auto i = (b), ie = (e); i < ie; i++)
#define pow2(x) (1ll<<(x))
#define all(x) begin(x), end(x)
#define until(x) while(!(x))
#define len(x) (int)size(x)

using namespace std;
using llong = long long;

template<class T> void __echo(const T & x, string sep) { cerr << x << sep; }
void __echo(const string& x, string sep) { cerr << "\"" << x << "\"" << sep; }
void __echo(const char& x, string sep = ", ") { cerr << "\'" << x << "\'" << sep; }
template<class T>
void __echo(const vector<T>& x, string sep) {
    cerr << "{";
    for (size_t i = 0; i < x.size(); i++) 
        __echo(x[i], i + 1 == x.size() ? "" : ", ");
    cerr << "}" << sep;
}

template<class T1, class T2>
void __echo(const pair<T1, T2>& x, string sep = ", ") 
{ cerr << "("; __echo(x.first, ", "); __echo(x.second, ""); cerr << ")" << sep; }

void __echo(istringstream& stream) {
    cerr << "\n";
}
template<size_t> struct Int {};
template<class Tuple, size_t Pos> void print_tuple(const Tuple& x, Int<Pos>) {
    __echo(get<tuple_size<Tuple>::value - Pos>(x), ", ");
    print_tuple(x, Int<Pos - 1>());
}
template<class Tuple>
void print_tuple(const Tuple& x, Int<1>) { cerr << get<tuple_size<Tuple>::value - 1>(x); }
template<class... Args>
void print_tuple(const tuple<Args...>& x) { print_tuple(x, Int<sizeof... (Args)>()); }
template<class... Args>
void __echo(const tuple<Args...>& x, string sep) { cerr << "("; print_tuple(x); cerr << ")" << sep; }
template<class T>
bool _char_const(const T& x) { return false; }
bool _char_const(const char* x) { cerr << x; return true; }
template<class T>
bool isCharConst(const T& x) { return false; }
bool isCharConst(const char* x) { return true; }
string trim(string x) {
    return string(begin(x) + x.find_first_not_of(' '), begin(x) + x.find_last_not_of(' ') + 1);
}
template<class T, class... Args>
void __echo(istringstream& stream, const T& x, Args... args) {
    static int cnt[200] = { 0 };//no bo po co to tworzyc od nowa?
    string name;
    do {
        string s;
        getline(stream, s, ',');
        for (auto c : s)
            cnt[(int)c]++;
        name += s + ',';
    } while (not(cnt['('] == cnt[')']
        &&
        cnt['['] == cnt[']']
        &&
        cnt['{'] == cnt['}']
        &&
        cnt['\"'] % 2 == 0
        &&
        cnt['\''] % 2 == 0));
    name.pop_back();//usuwamy ','

    if (!_char_const(x)) {
        cerr << trim(name) << " = ";
        __echo(x, "; ");
    }

    __echo(stream, args...);
}
#define echo(...) if(DBG) {istringstream str(#__VA_ARGS__); __echo(str, __VA_ARGS__); }
/////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////

#define TESTSETS 0
#define DBG 0
constexpr int mod = 998244353;

void solve()
{
    int Min = int(-1e9), Max = int(1e9);
    
    int n; cin >> n;
    vector<int> a(n);
    for (auto& ai : a)
        cin >> ai;

    pair<int, vector<int>> best_result(n + 42, { -1, -1,-1 });
    forx(up_parity, 0, 2) {
        vector<int> t = a;
        int result = 0;
        forx(i, 1, n) {
            bool up = (i % 2 == up_parity);
            if (up && t[i - 1] >= t[i]) {
                t[i] = int(1e9);
                result++;
            }
            else if (!up && t[i - 1] <= t[i]) {
                t[i] = int(-1e9);
                result++;
            }
        }
        best_result = min(best_result, { result, t });
    }

    cout << best_result.first << "\n";
    if (DBG)
        echo(best_result.second);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    if (TESTSETS)
        cin >> t;

    while (t--)
        solve();
}