#1493. 一首诗

一首诗

题目描述

文学大师 ZHY 创作了一首诗。

这首诗由 nn 个单词组成,为了方便表述,ZHY 将这首诗记录为一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\dots,a_n。创作完后,ZHY 立刻将自己的作品分享给了 YHZ。YHZ 在感受到了诗歌之美后,希望借此提高一下自己的文学素养,于是准备对这首诗中的诗句进行摘抄。

YHZ 认为一个“诗句”,应该是 a1,a2,…,ana_1,a_2,\dots,a_n 的一个连续子序列,诗句的长度即为子序列的长度。当然,他不会摘抄所有的诗句,而是只选择“优美的诗句”进行摘抄。由于不懂文法,YHZ 简单地认为一个诗句是“优美的”,当且仅当这个诗句中不存在两个相邻的重复单词。形式化的说,一个连续子序列 al,al+1,…,ara_l,a_{l+1},\dots,a_r(l≤rl\leq r)组成的诗句是“优美的”,当且仅当对于所有的 $l\leq i

输入格式

第一行两个正整数 n,qn,q。

第二行 nn 个整数 a1,a2,⋯ ,ana_{1},a_{2},\cdots,a_{n}。

接下来 qq 行,每行三个整数 li,ri,xil_{i},r_{i},x_{i},表示一次操作。

输出格式

输出 q+1q+1 行,表示第一次操作前和每次操作后的答案。

样例

4 2
1 2 3 4
1 2 1
2 3 1
4
6
5

题目来源:洛谷 P10255