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 \leq n \leq 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\%\) 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