```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(reader, &n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &a[i])
	}

	const NEG_INF = -1 << 30

	// Clean reimplementation with offset
	dp3 := make([]int, n+1)
	for i := range dp3 {
		dp3[i] = NEG_INF
	}
	dp3[0] = 1
	offset := 0

	// top2: two best (dp3[v]+offset) with different v
	top := [2]struct{ val, idx int }{{1, 0}, {NEG_INF, -1}}

	updateTop := func(val, idx int) {
		if val >= top[0].val {
			if idx != top[0].idx {
				top[1] = top[0]
			}
			top[0] = struct{ val, idx int }{val, idx}
		} else if idx == top[0].idx {
			// no update needed
		} else if val > top[1].val {
			top[1] = struct{ val, idx int }{val, idx}
		}
	}

	for i := 1; i < n; i++ {
		prev := a[i-1]
		gain1 := 0
		if a[i] != prev {
			gain1 = 1
		}

		curAiVal := dp3[a[i]] + offset // current dp value at a[i]
		maxExcl := top[0].val
		if top[0].idx == a[i] {
			maxExcl = top[1].val
		}

		best2Val := curAiVal // assign to other color, same value, no new segment
		if maxExcl != NEG_INF && maxExcl+1 > best2Val {
			best2Val = maxExcl + 1
		}

		// Step 1: add gain1 to all
		offset += gain1

		// Step 2: dp[prev] = max(dp[prev]+offset_already_added, best2Val)
		curPrevVal := dp3[prev] + offset
		if best2Val > curPrevVal {
			dp3[prev] = best2Val - offset
			curPrevVal = best2Val
		}

		// Update top2
		// After adding gain1, all values shifted. top values also shift.
		top[0].val += gain1
		if top[1].val != NEG_INF {
			top[1].val += gain1
		}

		// Now update for prev
		updateTop(curPrevVal, prev)
	}

	ans := NEG_INF
	for v := 0; v <= n; v++ {
		val := dp3[v] + offset
		if val > ans {
			ans = val
		}
	}

	fmt.Println(ans)
}
```