Sereja and Shuffling

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja have an array A = [A_{1}, A_{2}, ..., A_{N}], where N is an even integer. Let the function f(A) be defined by f(A) = (A_{1} + A_{2} + ... + A_{N/2}) − (A_{N/2+1} + A_{N/2+2} + ... + A_{N}). Sereja want to decrease the value f(A) by the unusual way.
Let A[l..r] denote the subarray [A_{l}, A_{l+1}, ..., A_{r}] of A. Sereja can shift some subarray A[l..r], where 1 ≤ l ≤ r ≤ N, then the array A will become [A_{1}, A_{2}, ..., A_{l1}, A_{l+1}, A_{l+2}, ..., A_{r}, A_{l}, A_{r+1}, A_{r+2}, ..., A_{N}]. For example we have the array A = [1, 2, 3, 4, 5] and we choose l = 2, r = 4, then after shifting we have the following array: A = [1, 3, 4, 2, 5].
Sereja can shift multiple times, however it's burdensome to shift many elements. Thus the sum of r − l + 1 should not exceed 2 × N.
Please help Sereja to find the way for decreasing the value f(A) = (A_{1} + A_{2} + ... + A_{N/2}) − (A_{N/2+1} + A_{N/2+2} + ... + A_{N}) as much as possible. Note that you don't have to minimize the value f(A), but the smaller value will give the higher score.
Input
Each test file contains only one test case.
The first line of input contains an integer N, denoting the length of the array. Then the next line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
Output
The first line should contain an integer q, denoting the number of shifts. Then the k^{th} line of the next q lines should contain two spaceseparated integers l and r, denoting the k^{th} shift, where 1 ≤ l ≤ r ≤ N.
Constraints
 2 ≤ N ≤ 100000, that is, 2 ≤ N ≤ 10^{5}
 0 ≤ A_{k} ≤ 1000000000, that is, 0 ≤ A_{k} ≤ 10^{9}
 N is even
Example
Input 1: 6 1 2 3 4 5 6 Output 1: 2 1 6 1 6 Input 2: 4 1 2 2 3 Output: 2 1 2 2 3
Scoring
Let INIT be the initial value of f(A), and S be the value of f(A) after shifting denoted by output. For each test file, your score is calculated as (INIT − S) / INIT, where you can assume INIT ≠ 0 for all official test files. Then the total your score is defined as the average of your score for the test files (see the next paragraph, for more details). The aim for this problem is to maximize the total your score.
We have 20 official test files. You must correctly solve and decrease the value f(A) strictly for all test files to receive Accepted. Invalid outputs, or S ≥ INIT for some test cases will lead Wrong Answer. You can assume that one can get Accepted for the official test files.
During the contest, the scores of the last 16 test files are 0, that is, the total your score is calculated by only the first 4 tests. After the contest, all solutions will be rescored by the average of the scores of the all 20 test files, and it will be the final score.
About Generating Tests
At first we choose 11 or 12 or 21 or 22 randomly, and each probability is 0.25. If we choose t here, then the test case is generated by the following TYPE t.
TYPE 11: N is chosen from [1, 10^{5}] uniformly and randomly. If N is odd, N is added by 1. Then each A_{k} is chosen from [0, 10^{9}] uniformly and randomly and independently.
TYPE 12: N is chosen from [1, 10^{5}] uniformly and randomly. If N is odd, N is added by 1. Then N real values y_{1}, y_{2}, ..., y_{N} are chosen from [0, 9) uniformly and randomly and independently. And each A_{k} is set floor(10^{yk}).
TYPE 21: A real value x is chosen from [2, 5) uniformly and randomly, and we set N = floor(10^{x}). If N is odd, N is added by 1. Then each A_{k} is chosen from [0, 10^{9}] uniformly and randomly and independently.
TYPE 22: A real value x is chosen from [2, 5) uniformly and randomly, and we set N = floor(10^{x}). If N is odd, N is added by 1. Then N real values y_{1}, y_{2}, ..., y_{N} are chosen from [0, 9) uniformly and randomly and independently. And each A_{k} is set floor(10^{yk}).
Author:  sereja 
Editorial  http://discuss.codechef.com/problems/SEASHUF 
Tags  aug14, challenge, greedy, heuristic, sereja 
Date Added:  6112013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 