How many increasing - 2

Input

The first line of the input contains the integer $N$, which is followed by $N$ integers on the next line. These integers, separated by one or more spaces, form the sequence (1 \le N \le 100000, and each integer's absolute value does not exceed 1{,}25 \cdot 10^5).

Output

Output a single line containing the number of strictly increasing subsequences, with the result given modulo $1000000009$ (10^9+9).

Examples