Masala H

Sizga uzunligi \(N\) ga teng bo'lgan, butun sonlardan iborat \(A\) massiv berilgan. Sizning vazifangiz massivdagi jozibali subsequencelar sonini sanashdan iborat.

Subsequence - massivdan 0 yoki bir nechta elementni o'chirishdan hosib bo'ladigan ketma-ketlik. 

Masalan [2,1,3] ketma-ketlikda 8 ta har xil subsequence bor, bular: [], [2], [1], [3], [2,1], [2,3], [1,3], [2,1,3]. 

Massivning turli o'rinlaridagi elementlarni o'chirishdan hosil bo'ladigan subsequence lar turlicha subsequence hisoblanadi. Masalan [2,2,3] ketma ketlikda ham 8 ta har xil subsequence bor, bular: [], [2] (2-element), [2] (3-element), [3], [2,2], [2,3](1 va 3 - element), [2,3] (2 va 3-element) , [2,2,3]

Jozibali subsequence - quyidagi shartlarning barchasini qanoatlantiradigan subsequence ga aytiladi:

• Elementlar soni kamida 2 ta bo'lgan subsequence;
• Elementlari qiymati bo'yicha aynan o'sish tartibida joylashgan subsequence;
• Ketma-ket kelgan ixtiyoriy 2 elementi orasidagi farq juft son bo'lgan subsequence.

Kirish faylining birinchi satrida bitta butun son, \(N(1 \le N \le 2 \times 10^5)\) - \(A\) massiv elementlari soni kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(A (1 \le A_i \le 10^9)\) massiv elementlari kiritiladi.

\(A\) massivda jami nechta jozibali subsequence mavjudligini aniqlang va natijani \(10^9+9\) ga bo'lgandagi qoldiqni chop eting.