## Editorial for HHPC1 P2 - Yuniformity Challenge

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

To make all numbers in the subarray the same in at most two steps, let's break down all situations:

**Situation 1 (achieved in zero steps):**

All numbers within the subarray are originally the same.

This can be checked using the Prefix Sum Array (PSA) by summing the absolute differences between each pair of adjacent numbers.

**Situation 2 (achieved in one step):**

Apply the second strategy to multiply all numbers within the subarray by . This implies that a is inside the subarray.

This can also be achieved using the PSA by counting the number of s in a prefix array.

**Situation 3 (achieved in two steps):**

If there is no zero, we can apply the first operation to add to all numbers within the array to create a zero in the first step, reducing the situation to the second situation, which requires another step. To create a zero at a position by adding , the number at that position must originally be its opposite, which is .

Implementing this might be more complicated, but it can also be done using the PSA. Iterate through all from to . Use an array to record the last position each number has appeared. For each , let be the last position where has appeared. For each query, check whether the maximum value in the prefix from to is greater than or equal to .

The intended time complexity is .

## Comments

I believe it should say you have to check whether the maximum value in the prefix from to is greater than or equal to .