나코더 39기 부원인 정후는 2022년 솔대제에 나코더의 무대를 선보이려고 한다. 무대의 이름은 '수열과 쿼리 333'으로, 1번부터 N번까지 일렬로 서 있는 학생들이 정후가 만든 Q가지 동작을 보여 줄 것이다. 각 동작은 두 종류 중 하나이고, 각 학생은 하나의 정수로 나타내어지는 매력을 가지고 있다.

첫 번째 종류의 동작은 x_i번 학생의 매력을 y_i로 바꾼다.
두 번째 종류의 동작은 l_i번 학생과 r_i번 학생 사이에서 서로 다른 학생 세 명이 나와 무대를 펼친다. 즉, l_i ≤ a < b < c ≤ r_i일 때 a 번, b 번, c 번 학생이 나와 주어진 동작을 마친다.

센터가 가진 매력이 독보적일수록 무대의 매력이 증가한다. i번 학생이 가진 매력을 Ai라고 말할 때 무대의 매력을 A_b - A_a - A_c로 계산한다.

정후는 열심히 준비한 만큼 완벽한 무대가 되기를 바란다. 정후를 위해 각 동작마다 세 명을 골라 무대의 매력의 최댓값을 알려 주자.

#6122 upload 39 done 16 how_to_reg 15

센터가 돋보여야 해 timer 3s memory 512MB

#6122

센터가 돋보여야 해 3s 512MB