Anh Tâm đang dạo chơi trên một quãng đường trắc trở, gồm có $n$ điểm ($n>1$), được đánh số hiệu từ 1 tới $n$. Mỗi điểm có một độ cao $a_i$ khác nhau. Điểm $i$ được gọi là một ngọn núi nếu nó cao hơn tất cả các điểm kề bên nó, được gọi là một thung lũng nếu nó thấp hơn tất cả các điểm kề bên nó.

Yêu cầu

Hãy xác định các ngọn núi và các thung lũng mà anh Tâm đặt chân tới.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa số nguyên $n$ ($n\ge 2$).
• Dòng tiếp theo chứa $n$ số nguyên $a_1,\ a_2,\ \ldots,\ a_n$ ($|a_i|\le{10}^3$).

Kết quả

Ghi ra đầu ra chuẩn

• Dòng đầu tiên chứa các số nguyên, là số hiệu của các ngọn núi mà anh Tâm đặt chân tới, theo thứ tự tăng dần.
• Dòng tiếp theo chứa các số nguyên, là số hiệu của các thung lũng mà anh Tâm đặt chân tới, theo thứ tự tăng dần.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Ví dụ

9
1 9 5 7 -4 6 2 2 -9

2 4 6
1 3 5 9

Giới hạn

Subtask 1 (100% số điểm): $n\le{10}^6$.