a277. TOI 2022/11 潛力組：上菜

題目描述

餐廳營業 N 分鐘。第 i 分鐘會做好一道種類為 Ci 的料理，也會有第 i 位客人到店，點選種類為 Di 的料理。料理不一定依客人到店順序製作。

上菜時必須遵守以下規則：

• 料理要依做好先後順序送出，前一道尚未送出時，後一道也不能送出。
• 若有多位客人點相同料理，必須優先送給最早到店且尚未收到料理的人。

每當一位客人發現比自己晚到的人先收到料理，怒氣就增加 1。即使同一分鐘連續送出多道料理，上菜的先後順序仍須計算。所有客人最後都能收到料理。請算出全部客人的怒氣總和。

輸入格式

第一行輸入 N，1 ≤ N ≤ 100000。 接下來 N 行，第 i 行輸入 Ci、Di，1 ≤ Ci、Di ≤ N。 兩個序列包含的各種料理數量完全相同。

輸出格式

輸出所有客人的怒氣總和，答案可能超過 32 位元整數範圍。

來源

TOI 2022 年 11 月潛力組〈上菜〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202211/Serving.pdf