김의 여정

잊힌 지 오래된 콤비나토리아 학원의 옛 홀에서, 재능 있는 수학자 김이 특이한 과제에 맞닥뜨린다. 김은 정수로 이루어진 오래된 수열을 발견했다. 이 수열은 전설적인 콤비나토리아의 신탁이 남긴 암호문으로 여겨지며, 김은 그 숨은 뜻을 풀고자 한다.

김의 임무는 수열 안에서 조화 부분수열이라 불리는 특정 패턴을 찾는 것이다. 조화 부분수열은 연속한 세 수의 합이 모두 짝수이고, 길이가 3 이상인 부분수열이다.

길이가 $n$인 수열 $a_i$ ($1 \le i \le n$)가 주어진다. 길이가 $m$인 부분수열은 $a_{b_1}, a_{b_2}, \ldots, a_{b_m}$이며, $1 \le b_1 < b_2 < \ldots < b_m \le n$을 만족하는 $m$개의 인덱스 집합으로 정해진다. 인덱스 집합이 다르면 서로 다른 부분수열로 본다.

이러한 부분수열의 개수는 매우 많을 수 있다. 김은 조화 부분수열의 총 개수를 $998\,244\,353$으로 나눈 나머지를 보고해야 한다.

첫 번째 줄에 수열의 길이를 나타내는 정수 $n$이 주어진다 ($3 \le n \le 2 \cdot 10^5$).

두 번째 줄에는 수열의 원소인 정수 $a_i$가 공백으로 구분되어 $n$개 주어진다 ($1 \le a_i \le 2 \cdot 10^5$).

조화 부분수열의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

문제 설명의 다섯 번째 예시는 보기 편하도록 수열을 세 줄로 나누어 적었지만, 실제 테스트 데이터에서는 한 줄로 주어진다. 이 예시의 조화 부분수열 실제 개수는 $4\,991\,221\,765 = 5 \times 998\,244\,353$이므로, $998\,244\,353$으로 나눈 나머지는 0이다.