Longest Alternating Subsequence Queries

Given a sequence \(a_{1\dots n}\) of length \(n\) and \(q\) modifications. A modification is described by two positive integers \(k\) and \(c\), meaning that you should update \(a_k=c\). Initially (before any modifications) and after every modification, you need to find the length of the longest alternating subsequence of \(a\).

A sequence \(p\) of length \(m\) is called an alternating sequence if and only if it has the form \[ p = \{x, y, x, y, \cdots\} \] with \(x \neq y\). In other words, the subsequence must alternate between two distinct values. Note that if no such subsequence of length at least 2 exists, the answer is 0.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \le n, q \le \text{small limits})\), representing the length of the sequence and the number of modifications.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the initial sequence.

Each of the following \(q\) lines contains two integers \(k\) and \(c\), indicating a modification where \(a_k\) is assigned the value \(c\).

outputFormat

Output \(q+1\) lines. The first line is the answer for the initial sequence, and the subsequent \(q\) lines are the answers after each modification. Each answer is a single integer denoting the length of the longest alternating subsequence of \(a\) (or 0 if no valid alternating subsequence exists).

sample

5 3
1 2 3 2 1
3 2
1 3
5 2

3
3
2
2