34856번 - 스티커 뽑기

문제

편의점에 새로운 빵이 출시됐다. 이 빵은 스티커 하나와 함께 포장되어 제공된다. 스티커에는 귀여운 사자와 곰 중 하나가 그려져 있다. 쿠옹이는 사자 스티커만을 선호하고, 단웅이는 곰 스티커만을 선호한다. 쿠옹이와 단웅이는 스티커를 모으기 위하여 편의점에서 빵 $N$개를 구매하고, 각 빵에 1ドル$번부터 $N$번까지 순서대로 번호를 부여하였다. 둘은 다음 규칙을 따라 스티커를 모으기로 했다.

1. 쿠옹이부터 시작하여, 아직 뜯지 않은 빵 중 번호가 가장 작은 빵을 뜯어 안에 들어있는 스티커를 가져간다. 만일 뜯을 빵이 없다면 과정을 종료한다.
2. 본인이 선호하는 스티커가 나왔다면, 차례를 바꾸지 않고 1번으로 돌아간다.
3. 본인이 선호하지 않는 스티커가 나왔다면, 차례를 상대에게 넘긴 후 1번으로 돌아간다.

어떤 빵도 뜯지 않은 상태에서 모든 빵을 뜯을 때까지 위 과정을 반복하는 것을 '스티커 뽑기'라고 정의한다.

당신은 어떤 빵에 어떤 스티커가 들어있는지 전부 알고 있다. 다음 $Q$개의 쿼리에 답해보자.

• $i$ $j$: $i$번과 $j$번 빵의 번호를 서로 바꾼 뒤 스티커 뽑기를 진행하면, 쿠옹이가 가져가는 사자 스티커 개수와 단웅이가 가져가는 곰 스티커 개수는 각각 몇 개인가?

각 쿼리는 누적되지 않음에 주의하라.

입력

첫째 줄에 빵의 개수 $N$이 주어진다. (2ドル \leq N \leq 3 \times 10^5$)

둘째 줄에 $a_1, a_2, ..., a_N$이 공백으로 구분되어 주어진다. ($a_i \in \{0, 1\}$)

$a_i$는 $i$번 빵에 들어있는 스티커의 정보를 나타내며, 0ドル$이면 사자 스티커, 1ドル$이면 곰 스티커를 의미한다.

셋째 줄에 쿼리의 수 $Q$가 주어진다. (1ドル \leq Q \leq 5 \times 10^5$)

이후 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

쿼리의 각 줄에는 정수 $i,ドル $j$가 공백으로 구분되어 주어진다. (1ドル \le i \lt j \le N$)

출력

각 쿼리에 대하여 쿠옹이가 얻는 사자 스티커 개수와 단웅이가 얻는 곰 스티커 개수를 $Q$개의 줄에 순서대로 출력한다.

제한

노트