구간 활성화

이 문제는 대화형(interactive) 문제입니다.

1번부터 $n$번까지 번호가 붙은 $n$개의 칸으로 이루어진 배열이 있습니다. $1 \le i \le j \le n$을 만족하는 정수 쌍 $(i, j)$마다 $i$번 칸부터 $j$번 칸까지(양 끝 포함)를 덮는 장벽이 하나씩 있습니다. 각 장벽은 활성 상태이거나 비활성 상태입니다. 활성 장벽이 하나도 덮지 않는 칸은 보이고, 그렇지 않은 칸은 보이지 않습니다.

각 장벽의 상태는 알 수 없습니다. 관찰할 수 있는 것은 보이는 칸의 개수뿐입니다. 임의의 장벽을 골라 상태를 뒤집을 수 있습니다. 활성 장벽은 비활성이 되고, 비활성 장벽은 활성이 됩니다. 목표는 모든 장벽을 비활성으로 만들어 모든 칸이 보이게 하는 것입니다.

예시에서 처음에는 장벽 $(1, 2)$와 $(2, 3)$만 활성 상태입니다. 두 장벽이 세 칸을 모두 덮으므로 첫 라운드에서 $k$는 $0$입니다.

• 장벽 $(2, 2)$를 뒤집으면 활성 장벽이 세 개가 되지만, 보이는 칸은 여전히 $0$개이므로 $k$는 $0$입니다.
• 장벽 $(1, 2)$를 뒤집으면 1번 칸이 보이게 되어 $k$는 $1$입니다.
• 장벽 $(2, 3)$을 뒤집으면 3번 칸도 보이게 됩니다. 이제 보이지 않는 칸은 2번 칸뿐이고, 이 칸은 활성 장벽 $(2, 2)$만 덮고 있으므로 $k$는 $2$입니다.
• 장벽 $(2, 2)$를 뒤집으면 모든 장벽이 비활성이 되어 모든 칸이 보입니다. $k = 3$을 읽은 뒤 프로그램이 종료됩니다.