CodeForces #448C Painting Fence [java]

import java.util.Scanner;

public class PaintingFence_448C {

	static int[] a;

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		a = new int[n];

		int result = 0;

		for (int i = 0; i < n; i++) {
			a[i] = scan.nextInt();
		}
		result = func(0, n);
		System.out.println(result);
		scan.close();
	}

	public static int func(int s, int e) {
		if (s != e) {
			int vans, hans;
			int min = Integer.MAX_VALUE;
			vans = e - s;
			for (int i = s; i < e; i++) {
				if (a[i] < min)
					min = a[i];
			}
			hans = min;
			
			int idx = s;
			for (int i = s; i < e; i++) {
				a[i] -= min;
				if (a[i] == 0 && i != e - 1) {
					if(i != idx) {
						hans += func(idx, i);
					}
					idx = i + 1;
				}
				if (i == e - 1) {
					if(a[i] == 0)
						hans += func(idx, i);
					else
						hans += func(idx, e);
				}
			}
			if (hans >= vans)
				return vans;
			else
				return hans;
		} else {
			return 0;
		}
	}
}