이 아이디어를 잘 생각해야 하는데, 같은 인덱스 쌍에다 연산을 2번 진행하면 그 구간이 전부 0이 됩니다. 그리고 이게 오히려 손해가 아닐 수도 있습니다. 이 아이디어를 통해 경우의 수를 나누면 이렇게 됩니다.


n==2일때: 원래 상태 유지하거나, (1,2)에 한번 하거나, 두 경우가 전부입니다. 2번 하면 그냥 0이 되니까 손해고, 두 경우 중에 최댓값을 찾아 주시면 됩니다.


n==3일때: 꽤 증명이 복잡해지는 건 이 부분인데, 결론부터 말하자면 1. 원래 상태 2. Max-Min으로 도배 3. 1번째로 도배 or 3번째로 도배


이 3가지 중에 2번째가 가능하다는 증명이 좀 걸렸는데, 이렇게 하면 됩니다. Max, Min이 1번째,3번째라면 (1,3) 한번이면 끝입니다. 2개가 인접할 때가 문제인데, 일단 이때 Max,min 있는 구간에 한번 쓰고, 중간 인덱스와 남은 한 인덱스에 2번 쓰고, 전체에 한번 하면 됩니다.


1번째나 3번째로 도배하는 것은 어렵지 않습니다. 나머지 2칸을 0으로 만들어 버린 뒤 전체 구간에 하면 됩니다.


n>=4일때: 무조건 Max로 도배하는 방법이 존재합니다. 다음과 같이 증명해 보겠습니다.


Max가 있는 인덱스를 기준으로 좌측에 남은 인덱스 수를 a, 우측에 남은 인덱스 수를 b라고 합시다. 그러면 a,b 둘 중 적어도 하나는 2 이상입니다. 2 이상인 쪽의 구간에 2번 써서 0으로 채워 줍시다. 그런 다음 Max도 포함해서 1번 써 주면 Max가 있는 인덱스를 포함해 2 이상인 쪽까지 Max로 채워집니다. 이제 Max 1칸만 남기고 다시 2번 써서 0으로 채워 준 다음, 전체 구간에 연산을 써 주면 전부 Max가 됩니다.


솔직히 저도 생각하는데 좀 걸렸고, 충분히 어려운 문제가 맞다고 생각합니다. 그래도 아이디어가 꽤나 재밌어서 좋은 문제라고 생각합니다