QOJ.ac

QOJ

Time Limit: 0.1 s Memory Limit: 512 MB
[+5]

# 7960. 排序大师

统计

题目描述

由于你是排序大师,你经常被路过的游客刁难,要求用一些奇怪的操作给序列排序。

由于你是远近闻名的排序大师,邻国的排序萌新小 I 慕名前来拜访,留下了一个长度为 n 的排列 a1,a2,an,并要求你用以下操作将排列升序排序:

  • 定义 aij={ai,ai+1,,aj}。选定 1ij<kln,交换 aijakl,即交换过后序列变为 a1i1,akl,aj+1k1,aij,al+1n

由于你是因精益求精而远近闻名的排序大师,你需要给出一个排序方案最小化操作次数。

输入格式

从标准输入读入数据。

输入的第一行一个整数 n(1n2,000) 表示序列长度,第二行 n 个整数 a1,a2,,an(1ain) 描述排列。

输出格式

输出到标准输出。

输出的第一行一个整数 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=5145326 变为 123456