Chef and Array

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has an array A[] of N elements denoted by A_{0}, A_{1}, ..., A_{N1}.
He thinks about M questions of following kind: "What is the maximum element among A_{i} where i lies between min{x, y} and max{x, y} both inclusive?"
You have to help Chef to find out sum of answers of all the M questions.
Method of generation of values x and y for all M questions:
You are given two integers x_{1} and y_{1} denoting values of x and y for the first question.
For the next questions, values of x_{i} and y_{i} are generated in the following way:
for i = 2 to M: x_{i} = (x_{i1} + 7) mod (N  1) y_{i} = (y_{i1} + 11) mod N
Here a mod b denotes the remainder of division of a by b.
Input
The first line contains a single integer N, denoting the number of elements in the array.
The second line contains N spaceseparated integers, denoting A_{0}, A_{1}, ..., A_{N1}.
The third line contains three spaceseparated integers M, x_{1} and y_{1}.
Output
Output a single integer denoting the sum of the answers to the questions.
Constraints and Subtasks
 2 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{8}
 1 ≤ A_{i} ≤ 10^{9}
 0 ≤ x_{1}, y_{1} ≤ N1
 N, M ≤ 10^{3}; 1 ≤ A_{i} ≤ 10^{5}
 N, M ≤ 10^{5}
 Original constraints
Example
Input: 3 1 2 3 3 0 1 Output: 7
Explanation
As ans_{1} + ans_{2} + ans_{3} = 2 + 2 + 3 = 7. So you have to print 7.
Author:  antoniuk1 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FRMQ 
Tags  antoniuk1, april15, easymedium, rmq, sparsetables 
Date Added:  17072014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions