I. Inequality Satisfying Subsequences
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A sequence of three positive integers $$$[a, b, c]$$$ is called a triangle if $$$a+b \gt c$$$ holds when reordered such that $$$a \leq b \leq c$$$.

A sequence of positive integers is triangle-free if no subsequence of length $$$3$$$ forms a triangle.

Given a sequence of positive integers $$$L$$$, count how many non-empty subsequences of $$$L$$$ are triangle-free. As the answer may be very large, you are only required to find the value modulo $$$998 \, 244 \, 353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 7\,000$$$) — the size of the input sequence.

The second line contains $$$n$$$ integers $$$L_1, L_2, \cdots, L_n$$$ ($$$1 \leq L_i \leq 10^9$$$) — the elements of the sequence $$$L$$$.

Output

Output the number of non-empty triangle-free subsequences modulo $$$998 \, 244 \, 353$$$ on one line.

Examples
Input
10
1 2 3 4 5 6 7 8 9 10
Output
173
Input
6
9 6 7 8 4 4
Output
23
Input
10
1 3 9 27 81 243 729 2187 6561 19683
Output
1023