수열 $A_1, A_2, \cdots, A_N$이 주어진다. 해당 수열의 부분수열 중 아래 조건을 만족하는 부분수열의 개수를 구하여라. 이때, 원래 수열에서 제거한 원소의 위치가 다르면 서로 다른 부분수열로 취급한다.

• 부분수열의 임의의 두 원소 $A_i, A_j$에 대해 $|A_i - A_j| \leq \min(A_i, A_j)$

어떤 수열의 부분수열이란 해당 수열에서 임의의 위치에 원소를 몇 개 제거한 수열이다. 이때 어떠한 원소도 제거하지 않아도 되며, 모든 원소를 제거해도 된다.

입력 형식

첫째 줄에 수열의 길이를 의미하는 정수 $N$이 주어진다. ($1 \leq N \leq 200\ 000$)

둘째 줄에 수열의 원소를 의미하는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 200\ 000$)

출력 형식

문제의 조건을 만족하는 부분수열의 개수를 출력한다. 개수가 많을 수 있으니, $998244353$으로 나눈 나머지를 구하여라. $998244353$은 소수이다.

예제

예제 1

입력

3
2 2 2

출력

8

예제 2

입력

3
1 2 3

출력

6