这是这个问题的更难版本。在这个版本中，$1 \le n \le 2\cdot10^5$。你可以通过锁定了问题来Hack这个问题。但是你只能通过锁定了前面的问题才能Hack前面的问题。

这个问题是要完成$n$个单选题。每个问题包含$k$个选项，只有一个选项是正确的。第$i$个问题的答案是$h_{i}$，如果你回答了问题$i$的正确答案$h_{i}$，你将获得$1$分，否则你将获得$0$分。已知在这个问题中，$h_1, h_2, \dots, h_n$是给定的。

然而，你的程序有一个错误。它将答案顺时针移动！考虑所有$n$个答案写在一个圆圈中。由于你程序中的错误，它们被顺时针旋转了一次。

正式地说，这个错误将问题$i$的答案移动到问题$i \bmod n + 1$。因此，问题$1$的答案移动到问题$2$，问题$2$的答案移动到问题$3$，依此类推，问题$n$的答案移动到问题$1$。

我们将所有$n$个答案放在一起称为一个答案套。总共有$k^n$种可能的答案套。

你 wondering, how many answer suits satisfy the following condition: 在顺时针移动一次后，新的答案套的总分严格大于原来的总分。你需要将结果模$998\,244\,353$。

例如，如果$n = 5$，并且你的答案套是$a=[1,2,3,4,5]$，它将提交为$a'=[5,1,2,3,4]$，因为有错误。如果正确的答案套是$h=[5,2,2,3,4]$，那么答案套$a$获得$1$分，答案套$a'$获得$4$分。由于$4 > 1$，答案套$a=[1,2,3,4,5]$应该被计入。

第一行包含两个整数$n$, $k$ ($1 \le n \le 2\cdot10^5$, $1 \le k \le 10^9$) — 问题的数量和每个问题的可能答案数量。

接下来的一行包含$n$个整数$h_1, h_2, \dots, h_n$, ($1 \le h_{i} \le k)$ — 各个问题的答案。

输出一个整数：满足给定条件的答案套的数量，模$998\,244\,353$。