a312. TOI 2023/03 潛力組：圖書館

題目描述

書架上依序有 N 本書，每本書都有一個編號，編號可能重複。請將整列書分成若干個非空的連續區段，每本書恰好屬於一個區段。

每個區段會各自依編號由小到大排序，再按原本的區段順序接回一列。你必須讓接回去的整列書也已經由小到大排好。相同編號的書沒有先後要求。請求出最多能分成幾個區段。

輸入格式

第一行是 N，第二行是 N 個書本編號。

• 1 ≤ N ≤ 1000000
• 每個編號介於 0 與 1000000000 之間。

輸出格式

輸出可行的最大區段數。

來源

TOI 2023 年 3 月潛力組〈圖書館〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202303/Library.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=k291