Dãy con tăng

Cho dãy số nguyên gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Người ta muốn chọn ra các dãy con thỏa mãn tất cả các điều kiện sau:

• Phần tử được chọn trước phải có số thứ tự nhỏ hơn phần tử được chọn sau.
• Phần tử được chọn trước phải có giá trị nhỏ hơn phần tử được chọn sau.
• Dãy con phải có ít nhất hai phần tử.

Ví dụ: Dãy số có 5 phần tử tương ứng với các giá trị 3 2 11 4 5

→ Có 9 dãy con thỏa mãn tất cả các điều kiện trên: (3, 11); (3, 4); (3, 5); (2, 11); (2, 4); (2, 5); (4, 5); (3, 4, 5); (2, 4, 5).

Yêu cầu: Hãy cho biết có bao nhiêu dãy con thỏa mãn tất cả các điều kiện trên?

Dữ liệu: vào từ file ARRINC.INP:

• Dòng đầu tiên chứa số nguyên dương $n$ ($n \le 30$).
• Trong $n$ dòng sau, dòng thứ $i$ là giá trị $a_i$ ($i = 1, 2, \dots, n$; $|a_i| \le 10^9$).

Kết quả: ghi vào file ARRINC.OUT một số nguyên là số dãy con thỏa mãn tất cả các yêu cầu.

• $n \le 30$;
• $|a_i| \le 10^9$.