NỐI XÍCH (MS0028)NGƯỜI TA CÓ N ĐOẠN XÍCH (N≤20000) MỖI ĐOẠN DÂY XÍCH L...

Bài 1: Nối xích (MS0028)Người ta có N đoạn xích (N≤20000) mỗi đoạn dây xích là một chuỗi các mắt xích nối với nhau. Các đoạn dây xích tách rời nhau. Mỗi đoạn xích không quá 20000 mắt xích.Bằng cách cắt ra một mắt xích sau đó gắn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn một dây xích là 1 đơn vị thời gian và được xem là bằng nhau với mọi mắt xíchNhiệm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất (hay số mắt xích bị cắt và hàn lại là ít nhất)Dữ liệu vào: Cho trong file NOIXICH.INP có cấu trúc như sau:Dòng đầu tiên là N, số đoạn xíchDòng tiếp theo ghi N số nguyên dương, số thứ i là số mắt xích có trong đoạn thứ i (1≤i≤N)Hai số cạnh nhau trên một dòng cách nhau ít nhất một khoảng trắngDữ liệu ra: Chương trình cần đưa ra file NOIXICH.OUT một số duy nhất là số đơn vị thời gian mà bạn cần để nối N đoạn xích đó