github.com/captn3m0/codechef.git

---
category_name: challenge
problem_code: SEASHUF
problem_name: 'Sereja and Shuffling'
languages_supported:
    - C
    - CPP14
    - JAVA
    - PYTH
    - 'PYTH 3.5'
    - CS2
    - 'PAS fpc'
    - 'PAS gpc'
    - RUBY
    - PHP
    - GO
    - NODEJS
    - HASK
    - SCALA
    - D
    - PERL
    - FORT
    - WSPC
    - ADA
    - CAML
    - ICK
    - BF
    - ASM
    - CLPS
    - PRLG
    - ICON
    - 'SCM qobi'
    - PIKE
    - ST
    - NICE
    - LUA
    - BASH
    - NEM
    - 'LISP sbcl'
    - 'LISP clisp'
    - 'SCM guile'
    - JS
    - ERL
    - TCL
    - PERL6
    - TEXT
    - CLOJ
    - FS
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: sereja
problem_tester: null
date_added: 6-11-2013
tags:
    - aug14
    - challenge
    - greedy
    - heuristic
    - sereja
editorial_url: 'http://discuss.codechef.com/problems/SEASHUF'
time:
    view_start_date: 1407749400
    submit_start_date: 1407749400
    visible_start_date: 1407749400
    end_date: 1735669800
    current: 1525454424
is_direct_submittable: false
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/AUG14/mandarin/SEASHUF.pdf) and [Russian](http://www.codechef.com/download/translated/AUG14/russian/SEASHUF.pdf).

Sereja have an array **A = \[A1, A2, ..., AN\]**, where **N** is an even integer. Let the function **f(A)** be defined by **f(A) = |(A1 + A2 + ... + AN/2) − (AN/2+1 + AN/2+2 + ... + AN)|**. Sereja want to decrease the value **f(A)** by the unusual way.

Let **A\[l..r\]** denote the sub-array **\[Al, Al+1, ..., Ar\]** of **A**. Sereja can shift some sub-array **A\[l..r\]**, where **1 ≤ l ≤ r ≤ N**, then the array **A** will become **\[A1, A2, ..., Al-1, Al+1, Al+2, ..., Ar, Al, Ar+1, Ar+2, ..., AN\]**. 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) = |(A1 + A2 + ... + AN/2) − (AN/2+1 + AN/2+2 + ... + AN)|** 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** space-separated integers **A1, A2, ..., AN**.

### 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 space-separated integers **l** and **r**, denoting the **k**th shift, where **1 ≤ l ≤ r ≤ N**.

### Constraints

- **2 ≤ N ≤ 100000**, that is, **2 ≤ N ≤ 105**
- **0 ≤ Ak ≤ 1000000000**, that is, **0 ≤ Ak ≤ 109**
- **N** is even

### Example

<pre>
<b>Input 1:</b>
6
1 2 3 4 5 6

<b>Output 1:</b>
2
1 6
1 6

<b>Input 2:</b>
4
1 2 2 3

<b>Output:</b>
2
1 2
2 3
</pre>### 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 1-1 or 1-2 or 2-1 or 2-2 randomly, and each probability is **0.25**. If we choose t here, then the test case is generated by the following _TYPE t_.

_TYPE 1-1_: **N** is chosen from **\[1, 105\]** uniformly and randomly. If **N** is odd, **N** is added by **1**. Then each **Ak** is chosen from **\[0, 109\]** uniformly and randomly and independently.

_TYPE 1-2_: **N** is chosen from **\[1, 105\]** uniformly and randomly. If **N** is odd, **N** is added by **1**. Then **N** real values **y1, y2, ..., yN** are chosen from **\[0, 9)** uniformly and randomly and independently. And each **Ak** is set **floor(10yk)**.

_TYPE 2-1_: A real value **x** is chosen from **\[2, 5)** uniformly and randomly, and we set **N = floor(10x)**. If **N** is odd, **N** is added by **1**. Then each **Ak** is chosen from **\[0, 109\]** uniformly and randomly and independently.

_TYPE 2-2_: A real value **x** is chosen from **\[2, 5)** uniformly and randomly, and we set **N = floor(10x)**. If **N** is odd, **N** is added by **1**. Then **N** real values **y1, y2, ..., yN** are chosen from **\[0, 9)** uniformly and randomly and independently. And each **Ak** is set **floor(10yk)**.