每年的 1024 程序員節(jié)日，黑馬程序員都會(huì)舉辦大型的慶?；顒?dòng)。今年的程序員節(jié)也不例外，每個(gè)班級(jí)的同學(xué)都發(fā)了橙子。

班級(jí)里有 n 名同學(xué)從前到后排成一排，且已經(jīng)得知了這些同學(xué)的成績(jī)，其中第 i 名同學(xué)的成績(jī)是 ai。班主任想根據(jù)同學(xué)們上個(gè)階段的考試成績(jī)來(lái)評(píng)定發(fā)橙子的數(shù)量。為了激勵(lì)成績(jī)優(yōu)秀同學(xué)，發(fā)橙子時(shí)需要滿足如下要求：

• 相鄰?fù)瑢W(xué)中成績(jī)好的同學(xué)的橙子必須更多。若相鄰的同學(xué)成績(jī)一樣，則它們分到的數(shù)量必須平等。
• 每個(gè)同學(xué)至少分配一個(gè)橙子

由于預(yù)算有限，班主任希望在符合要求的情況下發(fā)出盡可能少的橙子。請(qǐng)問，至少需要準(zhǔn)備多少橙子呢？

第一行是一個(gè)不超過 10^6 正整數(shù) n，表示學(xué)生數(shù)量。

接下來(lái)一行有 n 個(gè)不超過 10^9 的非負(fù)整數(shù) ai，表示第 i 個(gè)同學(xué)的成績(jī)。

5
3 4 5 4 3

9

樣例解釋：

每位同學(xué)拿到的橙子的數(shù)量分別是 1,2,3,2,1，所以至少需要準(zhǔn)備 9 個(gè)。