Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, ta định nghĩa ~f(l, r)~ là số cặp nghịch thế trong đoạn con ~a_l, a_{l+1}, \dots, a_r~. Nói cách khác, ~f(l, r)~ là hàm đếm số cặp ~(i, j)~ sao cho ~l \leq i < j \leq r~ và ~a_i > a_j~.

Yêu cầu: Tính tổng ~f(l, r)~ cho mọi đoạn con của mảng ~a~, tức là tính

$$\sum_{1 \leq l \leq r \leq n} f(l, r)$$

Input

Dòng đầu tiên chứa số nguyên ~n~ là kích thước mảng.

Dòng thứ hai chứa ~n~ số nguyên ~a_1~, ~a_2~, ~\dots~, ~a_n~ (với ~1 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Output

In ra đáp án modulo ~10^9 + 22213~, trên một dòng duy nhất.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n \leq 100~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq n \leq 2000~.

• Subtask ~3~ (chiếm ~40\%~ số điểm): ~1 \leq n \leq 2 \cdot 10^5~.

Sample Input 1

5
5 3 4 1 2

Sample Output 1

25

Sample Input 2

6
1 2 3 4 6 5

Sample Output 2

5