How many increasing - 2

Given a sequence of N integers, your task is to determine the number of strictly increasing subsequences within this sequence.

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 ≤ N ≤ 100000, and each integer's absolute value does not exceed 1.25·10^5).

Output

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

Examples