1747: 小C买泡芙（hard version)

easy version 和 hard version 在题目描述输入输出都是相同的，唯一的区别是两题的数据范围

众所周知，小C除了能学，他对吃也十分讲究。对于每一种他想买的东西，他总会喜欢一次性买齐每一种口味。

小C特别喜欢吃泡芙，于是，他正打算去学校的面包店买些泡芙。在学校的面包店里，泡芙是排成一排售卖的，每一个泡芙有着不同的口味（不同的口味将用不同的数字表示），而为了方便服务员进行包装，面包店还规定了顾客每次只能购买连续摆放的泡芙。

现在，小C来到了面包店，他希望以最少的价钱买齐每一种口味的泡芙，那么他至少得花多少钱呢

第一行输入三个整数n,m,k，表示一共有m种口味（每种口味用数字1到m表示）的n个泡芙，每个泡芙售价为k元

第二行输入n个整数，表示这n个泡芙，每个泡芙的口味

数据范围： 1<=n<=2e5,1<=m<=2e5,1<=k<=2e5

5 3 5
2 2 1 1 3

20