33749번 - Inequality Satisfying Subsequences 다국어

문제

A sequence of three positive integers $[a, b, c]$ is called a triangle if $a+b>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$.

입력

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 the number of non-empty triangle-free subsequences modulo 998ドル ,円 244 ,円 353$ on one line.

제한

힌트