D Codeforc 276

gistfile1.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <map>
using namespace std;
#define dprint(v) cout << #v"=" << v << endl
#define forr(i, a, b) for(int i=(a); i<(b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforn(i, n) for(int i=(n)-1; i>=0; i--)
#define forall(it,v) for(typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
typedef long long ll;
#define ii pair<int, int>
#define mkp make_pair
#define fst first
#define snd second
#define pb push_back
#define INF 1000000001

int a[1000100];
int n,t,r;
struct ar{
	ll val;
	int l;
	int u;	
} dp1[1000010], dp2[1000010];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("d.in", "r", stdin);
#endif
	while(cin >> n, n > 0){
		forn (i,n){
			scanf ("%d", &a[i]);
		}
		ll aux,aux2;
		dp1[0].val = dp2[0].val = 0;
		dp1[0].l = dp1[0].u = a[0]; 
		dp2[0].l = INF;
		dp2[0].u = -INF;
		forr (i,1,n){
			dp2[i]. val = max(dp2[i-1].val,dp1[i-1].val+dp1[i-1].u - dp1[i-1].l);
			dp2[i]. l = a[i];
			dp2[i]. u = a[i];
			
			aux = dp2[i-1].val + abs(a[i-1] - a[i]);
			if ((aux2 = dp1[i-1].val + max(dp1[i].u, a[i]) - min (dp1[i].l, a[i])) >= aux){
				dp1[i].val = dp1[i-1].val;
				dp1[i].u = max(dp1[i-1].u, a[i]);
				dp1[i].l = min(dp1[i-1].l, a[i]);
			}
			else{
				dp1[i].val = dp2[i-1].val;
				dp1[i].l = min (a[i], a[i-1]);
				dp1[i].u = max (a[i], a[i-1]);			
				
			}
		}
		
		cout << dp1[n-1].val + dp1[n-1].u - dp1[n-1].l << endl;
		//~ forn (i,n){
			//~ dprint(i);
			//~ dprint(dp1[i].val);
			//~ dprint(dp1[i].l);
			//~ dprint(dp1[i].u);
			//~ dprint( dp2[i].val);
			//~ dprint( dp2[i].l);
			//~ dprint( dp2[i].u);
	//~ }



		return 0;
		
	}
    return 0;
}