A sequence is given in the following format.
n
a0 a1,...,an−1
4 1 2 2 4
1 2 4
1≤n≤100,000
−1000,000,000≤ai≤1,000,000,000
a0≤a1≤...≤an−1