a302. TOI 2025/09 潛力組：片段排序

題目描述

一條紙帶上的 N 個數字互不相同。你可以沿相鄰數字間的界線剪開紙帶，再把各片段重新排序並接合；片段內的數字順序不能改變，也不能翻轉。給定原順序 a 與目標順序 b，請求出最少需要剪幾刀才能得到 b。

輸入格式

第一行為 N。第二、三行各有 N 個正整數，分別為 a 與 b。

• 2 ≤ N ≤ 200000
• 所有數字不超過 10⁹
• a 的數字互異，b 是 a 的一種排列。

輸出格式

輸出最少剪刀次數。

來源

TOI 2025 年 9 月潛力組〈片段排序〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202509/cut.pdf