B. Вилбур ба Массив

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Вилбур гахай дахиад л массивуудыг засч байна. Түүнд эхэндээ $n$ ширхэг тэгээр дүүргэгдсэн $a_{1}, a_{2}, ..., a_{n}$ массив байна. Нэг алхамд тэр дурын $i$ индексийг сонгож чадах ба бүх $a_{i}, a_{i + 1}, ... , a_{n}$ элементүүд дээр $1$-г нэмж чадна эсвэл бүх $a_{i}, a_{i + 1}, ..., a_{n}$ элементүүдээс $1$-г хасч чадна. Түүний зорилго бол $b_{1}, b_{2}, ..., b_{n}$ массивыг үүсгэх юм.

Мэдээж Вилбур уг зорилгоо хамгийн цөөн алхамд биелүүлэхийг хүсч байгаа ба таныг энэ утгыг тооцоолж өгөхийг хүсч байна.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 200 000$) байх ба $a_{i}$ массивын урт. Эхлээд $i$-н байрлал бүрийн хувьд $a_{i} = 0$ байх ба энэ массив нь оролтонд өгөгдөхгүй.

Оролтын хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $b_{1}, b_{2}, ..., b_{n}$ ($ - 10^{9} ≤ b_{i} ≤ 10^{9}$) байна.

Гаралт

Бүх $i$-н хувьд $a_{i} = b_{i}$ болгох зорилгоо биелүүлэхийн тулд Вилбурын хийх хэрэгтэй алхмуудын байж болох хамгийн бага тоог ол.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
1 2 3 4 5
Гаралт
5
Оролт
4
1 2 2 1
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр Вилбур дарааллуулан $1$, $2$, $3$, $4$, $5$ индексүүдийг сонгож харгалзах дагавар элементүүд дээр $1$-г нэмнэ.

Хоёр дахь жишээн дээр эхлээд Вилбур $1$ болон $2$ индексүүдийг сонгож харгалзах дагавар элементүүд дээр $1$-г нэмээд дараа нь $4$ индексийг сонгож $1$-г хасна.

Сэтгэгдлүүдийг ачааллаж байна...