神仙场。

A Number

原题链接

对每个数码分开考虑。对于一个数码来说，我们其实需要求的是一个最小的数 $i$ 使得

$$\sum_{j \le i} (d - S(j,d)) < 0$$

最后对每个数码的答案取最小值即可。

我们考虑这个东西怎么求。这个东西本身不太具有二分性，但是我们考虑对 $1 \sim 10^i - 1$ 求出这个前缀中的最小的前缀和以及整个的前缀和即可。然后我们就可以从高位到低位填数，从 $0$ 到 $9$ 枚举这位的数码，然后看看如果填入这个数后低位的最小前缀和会不会导致整个的最小前缀和 $<0$ ，即拿最小前缀和和前面的所有前缀和合并一下。

现在问题就是怎么确定位数了。如果实现了刚刚说的东西，直接从低到高位枚举位数，用之前求的那个东西看看是否仍然合法即可。

那么考虑怎么对 $1 \sim 10^i-1$ 求出这个前缀中最小的前缀和以及整个的前缀和。具体来说，我们设 $dp[i][k][0/1]$ 表示当前已经填了前 $i$ 位，其中有 $k$ 个数码 $d$ ，下一位从 $0$ 还是从 $1$ 开始填，此时得到的最小前缀和以及整个的前缀和是多少。转移就枚举下一位填啥合并一下即可。

这题需要高精，但是可以发现答案大小不超过 $10^{10a}$ ，即 $10^{160}$ 。所以直接上高精即可。

复杂度大概是 $O(l^3d^5)$ ，高精常数很小。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 166
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
const int iv2 = P + 1 >> 1;
int n;
int A[10];

struct num {
#define N 166
	int A[N + 1];
	void flip( ) {
		rep( i , 0 , N ) A[i] = 9 - A[i];
	}
	num( int x = 0 ) {
		int t = abs( x );
		mem( A );
		if( !x ) return;
		int le = 0;
		while( t ) A[le ++] = t % 10 , t /= 10;
		if( x < 0 ) {
			flip( );
			rep( i , 0 , N ) {
				if( A[i] != 9 ) { ++ A[i]; break; }
				A[i] = 0;
			}
		}
	}
	num operator + ( num x ) {
		num ret;
		int ad = 0;
		rep( i , 0 , N ) {
			ret.A[i] = x.A[i] + A[i] + ad;
			ad = 0;
			if( ret.A[i] > 9 ) ad = 1 , ret.A[i] -= 10;
		}
		return ret;
	}
	bool operator < ( num x ) const {
		if( x.A[N] != A[N] ) return A[N] == 9;
		per( i , N , 0 ) if( A[i] != x.A[i] ) return A[i] < x.A[i];
		return false;
	}
	void out() {
		int flg = 0;
		per( i , N , 0 ) {
			if( A[i] ) flg = 1;
			if( flg ) printf("%1d",A[i]);
		}
		puts("");
	}
};

//typedef ll num;

struct node {
	num mn , sum;
	node operator + ( node a ) {
		return (node) { min( mn , sum + a.mn ) , sum + a.sum };
	}
};

int k , cur;

int vis[MAXN][MAXN][2];
node dp[MAXN][MAXN][2];
node dfs( int len , int d , int st ) {
	if( len == 0 ) return (node) { num( -d + k ) , num( -d + k ) };
	if( vis[len][d][st] == cur ) return dp[len][d][st];
	vis[len][d][st] = cur , dp[len][d][st] = (node){ 0 , 0 };
	rep( i , st , 9 ) {
		dp[len][d][st] = ( dp[len][d][st] + dfs( len - 1 , d + ( i == cur ) , 0 ) );
	}
	return dp[len][d][st];
}

num solve( int c , int t ) {
	cur = c , k = t;
	node pr = (node){ 0 , 0 };
	int len = 0;
	while( ++ len ) {
		node cu = dfs( len , 0 , 1 );
		if( ( pr + cu ).mn < 0 ) break;
		pr = pr + cu;
	}
	num as = 0;
	int ps = 0;
	per( i , len , 1 ) rep( j , i == len , 9 ) {
		int cs = ps + ( j == cur );
		node cu = dfs( i - 1 , cs , 0 );
		if( ( pr + cu ).mn < 0 ) {
			ps = cs;
			as.A[i - 1] = j;
			break;
		}
		pr = pr + cu;
	}
	return as;
}

void solve() {
	num as;
	memset( vis , -1 , sizeof vis );
	rep( i , 0 , 9 ) {
		cin >> A[i];
		if( i ) as = min( as , solve( i , A[i] ) );
		else as = solve( i , A[i] );
	}
	as = as + -1;
	as.out();
}

signed main() {
//	freopen("in.in","r",stdin);
//	freopen("ot","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}

B Color

毒瘤题

我们要求：

$$\sum_{E \sube S} m^{|E|} [\text{E 中的边均两边黑色点不同的染色方案数}]$$

考虑进行一个容斥，把后面的条件看成恰好 $0$ 条边两边黑色点个数不同，然后按套路容斥：

$$\begin{aligned} &=\sum_{E \sube S} m^{|E|} \sum_{E' \sube E} (-1)^{|E'|} [\text{E' 中的边均两边黑色点相同的方案数}]\\ &=\sum_{E' \sube S} (-m)^{|E'|}[\text{黑点数相同}] \sum_{E' \sube E}m^{|E| - |E'|} \end{aligned}$$

可以发现后面那个东西本质上就是

$$\sum_{k = 0}^{|S| - |E|} \binom{|S| - |E|}{k} m^{k} = (m+1)^{|S| - |E|}$$

那么有

$$\begin{aligned} &=\sum_{E' \sube S} (-m)^{|E'|} (m+1)^{n - 1 - |E'|}[\text{黑点数相同}]\\ &=(m+1)^{n-1}\sum_{E' \sube S} (\frac{-m}{m+1})^{|E'|}[\text{黑点数相同}]\\ \end{aligned}$$

考虑一个可能成为答案的 $E’$ 集合。可以发现，当整张图存在黑点时， $E’$ 必须是某条路径的子集，我们不妨设这条路径是 $(u,v)$ ，则可以成为答案当且仅当 $u$ 在 $v$ 为根时子树内的黑点数和 $v$ 在 $u$ 为根时子树内的黑点数相同，切路径上其他点的非路径方向的子树内没有黑点。那么我们枚举一下这个相同的黑点数：

$$\sum_{k = 0}^{\min(sz_u,sz_v)} \binom{sz_u}{k} \binom{sz_v}{k}$$

这是一个组合恒等式（然而我场上忘了。。）

$$\sum_{k = 0}^{\min(sz_u,sz_v)} \binom{sz_u}{k} \binom{sz_v}{sz_v - k} = \binom{sz_u + sz_v}{sz_v}$$

但是需要注意，这里为了方便应用组合恒等式把 $k=0$ 的情况统计进去了，仔细思考一下会发现，其实 $k = 0$ 时，即所有点都不染色时，所有 $E’$ 都是合法的，但是这里我们统计了所有在一条链上的集合的在不染色时的和，最后还需要加上不染色时选择的边集不成一条路径的方案数。这个东西怎么算我们最后再说。

既然需要选择的点呈一个路径的样子，我们自然可以考虑到点分。考虑所有跨过当前根的非命运链，显然它长度 $\ge 2$ 。我们考虑 $\binom{sz_u + sz_v}{sz_v}$ 会被贡献多少次，可以发现当边集固定拿 $u,v$ 向父亲的边，且剩下的边随意拿的时，这个东西会被贡献上。也就是如果设路径长度为 $l$ ，那么贡献就是

$$\begin{aligned} &\binom{sz_u + sz_v}{sz_u}(m+1)^{n-1} \times (\frac{-m}{m+1})^2 \sum_{i=0}^{l-2} \binom{l-2}{i} (\frac{-m}{m+1})^i \\ &=\binom{sz_u + sz_v}{sz_u}(m+1)^{n-1} \times (\frac{-m}{m+1})^2 (\frac{1}{m+1})^{l-2} \\ \end{aligned}$$

然后我们考虑所有一端为根的命运链，显然我们可以暴力计算上面这个式子，因为算一次是 $O(1)$ 的。

然后如果我们把 $sz_u$ 作为一个点的下标，用 $\frac{-m}{m+1} (\frac{1}{m+1})^{d-1}$ 作为权值，就可以对整个树做一次卷积，再对所有儿子分别做然后减去了！看起来复杂度非常优秀，实际上呢，由于 $sz_u$ 是原树上的实际大小，所以获得了一个 $O(n^2\log n)$ 的优秀做法。

但是事实上，拼这个东西的过程是可以暴力，暴力的复杂度是 $O(siz^2)$ ，其中 $siz$ 是当前点分树的大小。

所以我们可以把这两个算法拼起来！设一个阈值 $blo = \sqrt{n \log n}$ ，然后如果整个点分树大于这个，就用第二个来算总的贡献，否则都用第一个，对于每个子树，如果超过阈值，我们用 NTT ，否则用暴力。这样看起来就得到了一个 $O(n \sqrt {n\log n})$ 的优秀做法。

然后我们来解决一下前面说的，加上不染色的边集不成一条路径的方案数。考虑求出有多少边集是路径子集，且涵盖边集的最小路径长度为 $l$ 的方案数。如果我们设长度为 $l$ 的路径有 $p_l$ 条，那么有

$$f_i = \sum_{j \ge i} p_j\binom{j-2}{i-2}$$

这个在最后做一次卷积即可。我们考虑怎么求出 $p$ ，不难发现 $p$ 也可以点分 NTT 解决。

最后还有一个毒瘤情况，当 $m = P-1$ 的时候，此时不存在 $\frac{1}{m + 1}$ 。但是可以发现此时只有全集会对答案造成贡献，也就是如果整棵树是链，则答案为 $2$ ，否则为 $1$ 。

最终复杂度 $O(n\sqrt{n \log n})$ 代码极其难写 + 难调。7kb +

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
//#pragma GCC optimize(3)
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
const int iv2 = P + 1 >> 1;
int n , m;
vi G[MAXN];

int J[MAXN] , iJ[MAXN] , p2[MAXN] , pw[MAXN] , pa[MAXN];
int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int C( int a , int b ) {
	if( b < 0 || a < 0 || a < b ) return 0;
	return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

inline void Inc( int& a , int b ) {
	a = ( a + b < P ? a + b : a + b - P );
}

int Wn[2][550006] , rev[MAXN];
void getwn( int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 ) {
		int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
		Wn[0][mid] = Wn[1][mid] = 1;
		for( int i = 1 ; i < mid ; ++ i )
			Wn[0][mid + i] = 1ll * Wn[0][mid + i - 1] * w0 % P,
					Wn[1][mid + i] = 1ll * Wn[1][mid + i - 1] * w1 % P;
	}
}
void getr( int len ) {
	int t = __builtin_ctz( len ) - 1;
	for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << t );
}
void NTT( int* A , int len , int typ ) {
	rep( i , 0 , len - 1 ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int k = 0 ; k < mid ; ++ k ) {
				int t1 = A[i + k] , t2 = 1ll * A[i + k + mid] * Wn[typ][mid + k] % P;
				A[i + k] = (t1 + t2 < P ? t1 + t2 : t1 + t2 - P) , A[i + k + mid] = (t1 < t2 ? t1 + P - t2 : t1 - t2);
			}
	if( typ == 1 ) for( int inv = Pow( len , P - 2 ) , i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * inv % P;
}

int vis[MAXN];

int sz[MAXN];
void afs( int u , int f ) {
	sz[u] = 1;
	rep( i , 0 , G[u].size() - 1 ) {
		int v = G[u][i];
		if( v == f || vis[v] ) continue;
		afs( v , u );
		sz[u] += sz[v];
	}
}
int tmn , trt , RT;
void cfs( int u , int f ) {
	int s = sz[RT] - sz[u];
	for( int v : G[u] ) if( v != f && !vis[v] ) {
			cfs( v , u );
			s = max( s , sz[v] );
		}
	if( s < tmn ) tmn = s , trt = u;
}
int getit( int u ) {
	tmn = 0x3f3f3f3f , trt = RT = u , afs( u , u ) , cfs( u , u );
	return trt;
}

int a , iva1 , blo;

int Fa[MAXN] , Siz[MAXN] , re , tds[MAXN];
void efs( int u , int f ) {
	tds[u] = 1;
	Fa[u] = f , Siz[u] = 1;
	for( int v : G[u] ) if( v != f ) {
			efs( v , u );
			Siz[u] += Siz[v];
		}
}

int siz[MAXN];
void dfs$( int u , int f ) {
	if( u == f ) siz[u] = n;
	sz[u] = 1;
	for( int v : G[u] ) if( v != f && !vis[v] ) {
			dfs$( v , u );
			if( v == Fa[u] ) siz[v] = n - Siz[u];
			else siz[v] = Siz[v];
			sz[u] += sz[v];
		}
}

int am , ivtt;

vi nod , cur;
int RR;
int xs[MAXN] , dis[MAXN];
void pfs( int u , int f ) {
	dis[u] = dis[f] + 1;
	cur.pb( u );
	for( int v : G[u] ) if( v != f && !vis[v] ) {
			xs[v] = xs[u] * 1ll * a % P;
			pfs( v , u );
		}
}

void Juan( int A[] , int n ) {
	int len = 1;
	while( len <= n ) len <<= 1;
	getr( len );
	NTT( A , len , 0 );
	rep( i , 0 , len - 1 ) A[i] = A[i] * 1ll * A[i] % P;
	NTT( A , len , 1 );
	rep( i , n , len - 1 ) A[i] = 0;
}
void Juan( int A[] , int B[] , int n ) {
	int len = 1;
	while( len <= n ) len <<= 1;
	getr( len );
	NTT( A , len , 0 ) , NTT( B , len , 0 );
	rep( i , 0 , len - 1 ) A[i] = A[i] * 1ll * B[i] % P;
	NTT( A , len , 1 ) , NTT( B , len , 1 );
	rep( i , n , len - 1 ) A[i] = 0;
}

int A[MAXN] , B[MAXN] , qd[MAXN] , tm[MAXN] , pt[MAXN] , kt[MAXN] , X[MAXN] , rX[MAXN] , xx[MAXN] , xp[MAXN];

ll res = 0;

void solve( int u ) {
	if( vis[u] ) return;
	dfs$( u , u );
	int dg = 0;
	RR = u;
	for( int v : G[u] ) if( !vis[v] ) ++ dg;
//	cerr << sz[u] << endl;
	if( sz[u] <= blo ) {
		dis[u] = 0;
		for( int v : G[u] ) if( !vis[v] ) {
				xs[v] = am;
				cur.clear();
				pfs( v , u );
				for( int x : cur ) {
					for( int y : nod )
						res = ( res + pw[n - 1] * 1ll * xs[x] % P * xs[y] % P * C( siz[x] + siz[y] , siz[x] ) ) % P;
					if( x != v )
						res = ( res + C( n - siz[v] + siz[x] , siz[x] ) * 1ll * xs[x] % P * pw[n - 1] % P * m ) % P;
					else
						res = ( res + C( n , siz[x] ) * 1ll * xs[x] % P * ( P - 1 ) % P * pw[n - 1] ) % P;
					for( int y : nod )
						Inc( pt[dis[x] + dis[y]] , 1 );
					Inc( pt[dis[x]] , 1 );
//			res = ( res + ( dg - 1 ) * 1ll * xs[x] % P * pw[n - 1] 	) % P;
				}
				nod.insert( nod.end() , cur.begin() , cur.end() );
			}
		nod.clear();
	} else {
		dis[u] = 0;
		for( int v : G[u] ) if( !vis[v] ) {
				xs[v] = am;
				cur.clear();
				pfs( v , u );
				if( sz[v] <= 1000 ) {
					for( int x : cur ) for( int y : cur ) {
							Inc( pt[dis[x] + dis[y]] , P - iv2 );
							Inc( rX[siz[x] + siz[y]] , P - iJ[siz[x]] * 1ll * xs[x] % P * xs[y] % P * iJ[siz[y]] % P * iv2 % P );
						}
					
				} else {
					for( int x : cur ) Inc( xp[dis[x]] , 1 ) , Inc( xx[siz[x]] , iJ[siz[x]] * 1ll * xs[x] % P );
					Juan( xp , n + 1 ) , Juan( xx , n * 2 + 1 );
					rep( i , 1 , n ) Inc( pt[i] , P - xp[i] * 1ll * iv2 % P ) , xp[i] = 0;
					rep( i , 1 , n * 2 ) Inc( rX[i] , P - xx[i] * 1ll * iv2 % P ) , xx[i] = 0;
				}
				for( int x : cur ) {
					if( x != v )
						res = ( res + C( n - siz[v] + siz[x] , siz[x] ) * 1ll * xs[x] % P * pw[n - 1] % P * m ) % P;
					else
						res = ( res + C( n , siz[x] ) * 1ll * xs[x] % P * ( P - 1 ) % P * pw[n - 1] ) % P;
					tm[dis[x]] ++;
					X[siz[x]] = ( X[siz[x]] + xs[x] * 1ll * iJ[siz[x]] ) % P;
					Inc( pt[dis[x]] , 1 );
				}
			}
		Juan( X , n * 2 + 1 ) , Juan( tm , n + 1 );
		rep( i , 1 , n * 2 ) Inc( rX[i] , X[i] * 1ll * iv2 % P ) , res = ( res + rX[i] % P * 1ll * J[i] % P * pw[n - 1] ) % P , rX[i] = X[i] = 0;
		rep( i , 1 , n ) Inc( pt[i] , tm[i] * 1ll * iv2 % P ) , tm[i] = 0;
	}
	
	vis[u] = 1;
	for( int v : G[u] ) if( !vis[v] ) solve( getit( v ) );
}

int rp[MAXN] , pfm[MAXN];

void solve() {
	getwn( 1 << 19 );
	cin >> n >> m;
	J[0] = iJ[0] = pw[0] = p2[0] = pfm[0] = 1;
	a = Pow( m + 1 , P - 2 );
	am = a * 1ll * m % P;
	rep( i , 1 , n )
		J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 ) , pw[i] = pw[i - 1] * 1ll * ( m + 1 ) % P , p2[i] = p2[i - 1] * 2 % P , pfm[i] = pfm[i - 1] * 1ll * ( P - m ) % P;
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	if( m == P - 1 ) {
		int as = 1 , noc = 0;
		rep( i , 1 , n ) if( G[i].size() > 2 ) { noc = 1; break; }
		if( !noc ) as = as * 2 % P;
		cout << as << endl;
		return;
	}
	blo = 6000;
	efs( 1 , 1 );
	solve( getit( 1 ) );
	rep( t , 0 , n - 2 ) tm[t] = pt[t + 2] * 1ll * J[t] % P;
	rep( t , 0 , n ) X[t] = iJ[n - t];
	int len = 1;
	while( len <= n + n ) len <<= 1;
	getr( len );
	NTT( tm , len , 0 ) , NTT( X , len , 0 );
	rep( i , 0 , len - 1 ) tm[i] = tm[i] * 1ll * X[i] % P;
	NTT( tm , len , 1 );
	rep( i , 0 , n ) tm[i] = tm[i + n] * 1ll * iJ[i] % P;
	res = ( res + p2[n] * 1ll * pw[n - 1] ) % P;
//	cout << res << endl;
	rep( i , 2 , n - 1 ) {
		res = ( res + ( C( n - 1 , i ) + P - tm[i - 2] ) % P * 1ll * pfm[i] % P * pw[n - 1 - i] % P ) % P;
	}
	cout << res << endl;
}

signed main() {
//	freopen("color5_1.in","r",stdin);
//	freopen("ot","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}

C 序列

先考虑相邻不相同的情况。首先考虑波峰，可以发现波峰的取值一定是波峰这一段的最小值。

考虑如果有长度 $> 3$ 的波峰。如果左右有一边不是最小值，那么一定可以把最左边 / 最右边往上抬，再把另一个往下降得到一个一样优的解。

否则，可以发现，如果一个峰的长度大于 $3$ ，那么一定是 $x,x+a,x,x+b,\dots,x$ 这样的情况（可以发现如果不是这样一定可以调整）。最后可以证明，一个数如果作为波峰，那么这个数只能取到左右的最小值。

然后考虑波谷，波谷的取值只有两种，要么是这段的最小值，要么是旁边波峰的最小值减 $1$ 。最后类似的去讨论各种情况后可以发现，对于波谷中的每个位置，只有这么几种取值之一：这个位置左右的最小值，左右隔一个位置的最小值，以及左右值减 $1$ ，以及左右隔一个位置的值减 $1$ 。

相邻相同的情况可以类似讨论，最后可以发现，一个位置只有 $7$ 种取值，所以直接 $dp$ 即可。

这种题比较靠谱的做法还是取相邻十个位置的值以及值减 $1$ ，然后拍一拍发现没问题。因为讨论确切下界的过程非常繁琐，不适合在场上做（而且场上做了也不一定能想清楚所有情况）。

复杂度 $O(n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
const int iv2 = P + 1 >> 1;
int n;
int dp[MAXN][9][2];
int A[MAXN];

int getit( int x , int c ) {
	if( c == 0 ) return A[x];
	if( c <= 2 ) return x + c > n ? 1e9 : A[x + c];
	if( c <= 4 ) return x - c + 2 < 1 ? 1e9 : A[x - c + 2];
	if( c <= 6 ) return x + c - 4 > n ? 1e9 : A[x + c - 4] - 1;
	return x - c + 6 < 1 ? 1e9 : A[x - c + 6] - 1;
}

void Ckm( int& a , int b ) {
	a = min( a , b );
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%lld",A + i);
	memset( dp , 0x3f , sizeof dp );
	rep( c , 0 , 8 ) rep( w , 0 , 1 ) {
		if( A[1] < getit( 1 , c ) ) continue;
		dp[1][c][w] = A[1] - getit( 1 , c );
	}
	rep( i , 2 , n ) rep( las , 0 , 8 ) rep( w , 0 , 1 ) if( dp[i - 1][las][w] < 1e18 ) {
		int x = dp[i - 1][las][w] , ls = getit( i - 1 , las );
		rep( c , 0 , 8 ) {
			int cr = getit( i , c );
			if( A[i] < cr ) continue;
			if( cr == ls ) Ckm( dp[i][c][w] , x + A[i] - cr );
			else if( ( cr < ls ) != w ) Ckm( dp[i][c][cr < ls] , x + A[i] - cr );
		}
	}
//	cout << dp[4][1][0] << endl;
	int res = 1e18;
	rep( c , 0 , 8 ) rep( w , 0 , 1 ) Ckm( res , dp[n][c][w] );
	cout << res << endl;
}

signed main() {
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}