Problem Statement

You are given a sequence $A=(A_1,\ldots,A_N)$ of length $N$. You perform the following operation exactly once.

• Choose a pair of integers $(L,R)$ such that $1\leq L \leq R \leq N$. Replace each of $A_L,A_{L+1},\ldots,A_R$ with $A_L$.

How many different sequences are possible as $A$ after the operation?

Constraints

• All input values are integers.
• $1 \leq N \leq 10^6$
• $1\leq A_i \leq N$

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Output the answer.