题目描述
由于你是排序大师,你经常被路过的游客刁难,要求用一些奇怪的操作给序列排序。
由于你是远近闻名的排序大师,邻国的排序萌新小 I 慕名前来拜访,留下了一个长度为 n 的排列 a1,a2⋯,an,并要求你用以下操作将排列升序排序:
- 定义 ai∼j={ai,ai+1,⋯,aj}。选定 1≤i≤j<k≤l≤n,交换 ai∼j 和 ak∼l,即交换过后序列变为 a1∼i−1,ak∼l,aj+1∼k−1,ai∼j,al+1∼n。
由于你是因精益求精而远近闻名的排序大师,你需要给出一个排序方案最小化操作次数。
输入格式
从标准输入读入数据。
输入的第一行一个整数 n(1≤n≤2,000) 表示序列长度,第二行 n 个整数 a1,a2,⋯,an(1≤ai≤n) 描述排列。
输出格式
输出到标准输出。
输出的第一行一个整数 s 表示你给出的方案的步数,接下来 s 行每行四个整数 i,j,k,l 表示一次操作。若有多个方案,输出任意一个即可。
样例1输入
6
1 4 5 3 2 6
样例1输出
1
2 3 5 5
样例1解释
选定 i=2,j=3,k=5,l=5,145326 变为 123456。