Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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$-г хасна.