Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Reverse
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3312 Accepted: 1069 Special Judge

Description

You will be given a list of n integers S = {1, 2, ... , (n-1), n}, please write a program to calculate the minimum number of instructions required to change the list in descending order {n, (n-1), ..., 1}. Let S[i] denote the i-th element of S, 1 ≤ in.

Each instruction takes a successive subsequence and removes that subsequence from the list, then insert that subsequence into any position of the list as a parameter. Each instruction can be represented by three numbers (pos1,length,pos2)，which means we will remove subsequence S[pos1] ..... S[pos1+length-1], then insert them after the S[pos2] (pos2=0 will insert it at the beginning). We always have: 1 ≤ pos1n, 1 ≤ lengthn+1-pos1, 0 ≤ pos2n-length

For example:
The list S = {4,6,5,3,1,2}，instruction (2,3,0) to get {6,5,3,4,1,2}
The list S = {4,6,5,3,1,2}，instruction (3,1,2) to get {4,6,5,3,1,2}
The list S = {4,6,5,3,1,2}，instruction (4,3,1) to get {4,3,1,2,6,5}
The list S = {4,6,5,3,1,2}，instruction (2,4,2) to get {4,2,6,5,3,1}

Input

The input contains one integer n. 1 ≤ n ≤ 100

Output

The first line of output contains one integer C denoting the number of instructions.
Following C lines, each contains three numbers (pos1, length, pos2) for one instruction. If there are many such instructions, you can output any one of them.

Sample Input

```Sample Input 1
3
Sample Input 2
4
```

Sample Output

```Sample Output 1
2
1 1 2
1 1 1
Sample Output 2
3
1 2 2
1 1 1
3 1 3```

Source

[Submit]   [Go Back]   [Status]   [Discuss]