Candies

$\operatorname{pos}_x$를 $x$번 아이가 처음 서 있던 위치라고 하자.

어떤 아이가 현재 위치 $p$에 있고 사탕을 $c$개 가지고 있다고 하자. 한 번의 조작에서 맨 왼쪽 아이는 오른쪽으로 $2$칸 이동하고 사탕을 $1$개 받는다. 나머지 두 아이는 왼쪽으로 $1$칸 이동하고 사탕을 $1$개 받는다. 따라서 모든 아이에 대해 항상 $p+c\equiv \operatorname{pos}_x\pmod 3$이 성립한다.

조작되는 세 아이의 사탕 수는 같다. 따라서 연속한 세 위치에 있는 아이들의 최초 위치를 $3$으로 나눈 나머지는 서로 다르다. 그러므로 최초 위치가 같은 나머지를 가지는 두 아이의 상대적인 순서는 절대로 바뀌지 않는다.

따라서 처음에 위치 $i$와 $i+3$에 있던 아이는 최종 상태에서도 같은 순서를 유지해야 한다. 최종 상태에서는 번호가 증가하는 순서이므로 모든 $1\le i\le N-3$에 대해 $P_i<P_{}$이어야 한다. 하나라도 만족하지 않으면 답은 이다.

이제 이 조건이 성립한다고 하자.

최종적으로 $i$번 아이는 위치 $i$에 있어야 한다. 이 아이의 최초 위치가 $\operatorname{pos}_i$이고 마지막 사탕 수가 $H_i$라면, 앞의 불변량으로부터 을 얻는다.

현재 각 위치에 있는 아이의 사탕 수만 배열로 보자. 사탕 수가 모두 $h$인 연속한 세 아이를 조작하면 위치별 사탕 수는 $h,h,h$에서 $h+1,h+1,h+1$로 변한다. 따라서 한 번의 조작을 막대그래프 위에 길이 짜리 수평 블록 하나를 올리는 것으로 생각할 수 있다.

최종 사탕 수가 $H_1,H_2,\ldots,H_N$이라고 하자. 임의의 양의 정수 에 대해 인 위치들만 보면, 각 극대 연속 구간의 길이는 반드시 의 배수여야 한다. 한 층은 길이 인 블록들로만 만들어지기 때문이다.

반대로 이 조건을 만족하면 실제로 만들 수 있다. 낮은 층부터 차례대로 보면서, 높이 $k$ 이상인 각 연속 구간을 왼쪽부터 세 칸씩 나누어 조작하면 된다. 해당 층을 만들기 직전에는 선택한 세 위치의 사탕 수가 모두 $k-1$이므로 조작은 항상 가능하다.

따라서 이제 각 $i$에 대해 $H_i\equiv \operatorname{pos}_i-i\pmod3$을 만족시키면서, 모든 높이에서 연속 구간의 길이가 의 배수가 되도록 을 정하면 된다. 조작 한 번은 전체 사탕 수를 정확히 증가시키므로 필요한 조작 횟수는 이다.

$H_i$를 왼쪽부터 결정하자. 각 높이 $k$에 대해 $S_k$를 현재까지 높이 $k$에서 이어지고 있는 마지막 연속 구간의 길이를 으로 나눈 나머지라고 하자.

$S_k\ne0$이면 높이 $k$의 마지막 구간이 아직 완성되지 않았다는 뜻이다. 따라서 다음 위치 역시 높이 $k$ 이상이어야 한다. $M$을 인 가장 큰 라고 하면 다음 높이는 반드시 이상이다. 그런 가 없다면 으로 둔다.

한편 $H_i$는 $H_i\equiv \operatorname{pos}_i-i\pmod3$을 만족해야 한다. 따라서 이상인 정수 중 이 합동식을 만족하는 가장 작은 값을 로 선택한다.

이 선택은 항상 최적이다. $M$보다 작은 값을 선택하는 것은 아직 완성되지 않은 어떤 층의 구간을 그대로 끝내므로 불가능하다. 반대로 선택한 값보다 같은 나머지를 가지는 더 큰 값을 고르려면 적어도 $3$을 더해야 한다. 이렇게 새로 추가되는 세 층은 기존의 미완성 구간을 완성하는 데 아무 도움도 주지 않고, 새로운 미완성 구간만 만든다. 따라서 더 높은 값을 선택할 이유가 없다.

$H_i$를 정한 뒤에는 높이 $1$부터 $H_i$까지의 마지막 구간 길이가 모두 $1$씩 증가하므로 에 각각 을 더하고 으로 나눈 나머지를 취한다.

모든 위치를 처리한 뒤 $S_k\ne0$인 높이가 하나라도 남아 있다면 마지막 연속 구간의 길이가 $3$의 배수가 아닌 층이 존재하므로 불가능하다. 모두 $0$이라면 지금까지 선택한 높이들이 최적이다.

필요한 연산은 $S_1,\ldots,S_H$에 $1$을 더하는 prefix 갱신과, $S_k\ne0$인 가장 큰 를 찾는 것이다. Lazy Propagation을 사용하는 세그먼트 트리로 처리할 수 있다.

각 노드에는 해당 구간에 등장하는 $S_k$의 값들을 $3$비트 마스크로 저장한다. bit $j$는 그 구간에 $S_k=j$인 위치가 존재한다는 뜻이다. 구간 전체에 을 더하고 으로 나눈 나머지를 취하면 상태 가 각각 으로 바뀌므로 비트 마스크를 한 칸 순환시키면 된다.

$S_k\ne0$인 가장 큰 $k$를 찾을 때는 오른쪽 자식부터 확인하면서 상태 $1$ 또는 $2$가 존재하는 쪽으로 내려가면 된다.

새로운 $H_i$는 현재의 $M$보다 최대 $2$만 크므로 모든 높이는 $2N$ 이하만 관리하면 충분하다.

시간 복잡도는 $O(N\log N)$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6