This question came up when i misread a USACO question. The actual USACO question is much easier (I think).

The question

Let's suppose that we have a game played as follows:
In the beginning, we have two arrays V and W, both of size n. W is filled with some colors (the colors are represented as numbers from 1 to 100000000) and V is a blank array (all the cells have zero as color). We play in rounds, and at each round we can choose for every color at most one segment [L, R] and paint all of V's cells from L to R with the given color. In a round, we can only choose for every color at most one segment, and all choosen segments need to be disjoint. We need to print the minimum number of rounds need to transform V into W.

Sample Input:
8 (The value of N)

3 4 3 7 3 2 2 4 (the array W)

Sample Output :
2

Explanation: In the first round we can paint the segment [0,4] with the color 3 , the segment [5,6] with the color 2 and the segment [7,7] with the color 4. V == 3 3 3 3 3 2 2 4
In the second round we can paint the segment [1,1] with the color 4 and the segment [3,3] with the color 7 , and V == W
PS: I don't have a polynomial solution yet , and i took a while thinking about this, if anyone can solve this in polynomial time, or give me some bound of the complexity, it will be great :)
Edit : Bump 1!