Chú ý: Chỉ sử dụng ngôn ngữ C cho vấn đề này.

Cho dãy số có $n$ phần tử $u_1,u_2,...,u_n$. Với mỗi $i$ chạy từ $1$ tới $n$, bạn hãy xác định ba số nguyên $a$, $b$, $c$ với ý nghĩa như sau:

• $a$ là phần tử nhỏ nhất trong dãy $u[1...i]$ (dãy con từ $1$ tới $i$).
• $b$ là số lần phần tử có giá trị bằng $a$ xuất hiện trong dãy $u[1..i]$.
• $c$ là chỉ số nhỏ nhất của phần tử có giá trị bằng $a$.

Đầu vào

Dòng đầu chứa số nguyên dương $n$ $(2\le n\le {10}^6)$, số phần tử của dãy $(u)$.

Dòng tiếp theo gồm $n$ số nguyên là các phần tử của dãy $(u)$ có giá trị tuyệt đối không vượt quá ${10}^7$.

Đầu ra

$n$ dòng, mỗi dòng chứa ba số nguyên là kết quả của bài toán.

Subtask

$30\mathrm{\%}$ số test có $n\le 1000$.

Ví dụ

Đầu vào:

5
1 9 -1 -1 -2

Đầu ra:

1 1 1
1 1 1
-1 1 3
-1 2 3
-2 1 5