TLEoj Contest #03 - Đảo ngược đoạn con

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

HoBaoPhuc2009, _inaccurate

Dạng bài

dbthuan208 đang rất thích tin học, đặc biệt là những bài toán về tập hợp các số nguyên. Nhận thấy được sở thích bạn mình, HoBaoPhuc2009 đã nghĩ ra một bài để thách thức bạn mình, đề bài như sau:

Ta gọi dãy số $a$ được gọi là dãy tăng nghiêm ngặt khi với mọi $1\le i<n$ thì $a_i<a_{i+1}$

Hai đoạn $[l,r]$ và $[u,v]$ được cho là không giao nhau khi không có giá trị $i$ nào thỏa mãn đồng thời $l\le i\le r$ và $u\le i\le v$

Yêu cầu: Cho một dãy số $a$ gồm $n$ phần tử, hãy chọn ra một số đoạn $[l,r]$ không giao nhau trong mảng $a$ sao cho khi đảo ngược tất cả các đoạn này trong dãy số (tức là biến đổi đoạn $a_l,a_{l+1},\dots,a_r$ thành $a_r,a_{r-1},\dots,a_l$ ) thì dãy số $a$ trở thành một dãy tăng nghiêm ngặt và số đoạn được chọn là ít nhất có thể.

dbthuan208 thấy đây là một bài toán quá khó đối với anh ấy, bạn có thể giúp anh ấy chứ?

Input, Output và Subtasks

Input

Dòng thứ nhất gồm 1 số nguyên dương $n$ cho biết độ dài của dãy $a$ ( $1\le n\le 10^6$ )
Dòng thứ hai gồm $n$ số nguyên $a_1,a_2,\dots,a_n$ ( $1\le a_i\le 10^9$ )

Output

Dòng đầu tiên xuất ra 1 số $k$ là số lượng dãy được chọn, sau đó là $k$ dòng tiếp theo, mỗi dòng gồm 2 số biểu thị đoạn được chọn, các số được cách nhau bởi một dấu khoảng trắng. Các đoạn con được xuất ra theo thứ tự tăng dần theo vị trí.
Trường hợp không có dãy thỏa mãn thì xuất -1

Scoring

Subtask 1 ( $30\%$ ): $1\le n\le 10^3$
Subtask 2 ( $30\%$ ): $1\le n\le 10^5$
Subtask 3 ( $40\%$ ): Không có ràng buộc gì thêm

Sample

Input

10
3 2 1 6 5 4 9 8 7 10

Output

Bình luận

Không có bình luận nào.