# Matchsticks | codechef solution

## Problem

Chef Ceil has some matchsticks in his kitchen.

Detail of matchsticks:

There are $�$ matchsticks in total. They are numbered from to $0$ to $�-1$ inclusive. The ${�}^{�ℎ}$ matchstick takes ${�}_{�}$ time to burn when lighted at one end, and it burns at a uniform rate.

If lighted at both ends simultaneously, the matchstick will take only half of the original time to burn down.

Arrangement:

He ties rear end of the all the matchsticks together at one point and the front end is kept free. The matchstick numbered $�$ is adjacent to matchstick numbered $�+1$ for all $0\le �\le �-2$.

Bodies of matchsticks do not touch each other, except at the rear end.

There are $�$ queries, in each query we ask: If he lights the free end of all matchsticks numbered between $�$ and $�$ inclusive, what will be the time needed for all matchsticks to get completely burnt?

### Input

• First line of input contains a single integer $�$.
• The next line contains $�$ space separated integers, the ${�}^{�ℎ}$ of which is ${�}_{�}$
• The next line contains a single integer $�$
• The next $�$ lines each contain two space separated integers - $�$ and $�$. The ${�}^{�ℎ}$ line represents the ${�}^{�ℎ}$ query.

### Output

For each query, print the answer on a new line.

### Constraints:

• $1\le �\le 1{0}^{5}$
• $1\le {�}_{�}\le 1{0}^{8}$
• $1\le �\le 1{0}^{5}$
• $0\le �\le �\le �-1$

### Sample 1:

Input
Output
1
5
1
0 0
5.0

### Sample 2:

Input
Output
2
3 5
1
0 1
4.0

### Sample 3:

Input
Output
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10
9.0

### Explanation:

Test Case 3: , in the figure above, yellow colored matches are lighted by a lighter simultaneously.

The numbers indicate the time required to burn that matchstick (if lighted at one end).

Now the first lighted matchstick will completely burn in $5$ seconds. Then it will light up all the rest matches from the rear end.

Some matches will have fire at both ends and thus after $5$ seconds, they will start burning with twice the original rate.

Thus time taken for matches to burn completely will be : (from left to right): $8.0$$9.0$$7.0$$6.0$$5.0$$6.0$$7.0$$6.0$$7.5$$5.0$$8.5$$8.0$$6.0$$6.0$$7.0$$6.0$$8.0$$7.0$. So, the answer will be $9.0$ (the maximum among these).

Code(C++):-

#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX

using namespace std;

int t[2*100005];
int t2[2*100005];

vector <int> a;

int n = 0;

void buildmin() {
for (int i = 0;i<n;i++) {
t[i+n]=a[i];
t2[n+i]=a[i];
}
for (int i = n-1;i>0;i--) {
t[i]=min(t[2*i],t[2*i+1]);
t2[i]=max(t2[2*i],t2[2*i+1]);
}
}

int qmin(int l, int r) {
l+=n; r+=n;
int res = inf;
while (l<=r) {
if (l%2==1) {
res=min(res,t[l++]);
}
if (r%2==0) {
res=min(res,t[r--]);
}
r/=2; l/=2;
}
return res;
}

int qmax(int l, int r) {
l+=n; r+=n;
int res = 0;
while (l<=r) {
if (l%2==1) {
res=max(res,t2[l++]);
}
if (r%2==0) {
res=max(res,t2[r--]);
}
r/=2; l/=2;
}
return res;
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout << setprecision(1) << fixed;
cin >> n;
a.resize(n,0);
for (int i = 0;i<n;i++) {
cin >> a[i];
}
buildmin();
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int mn = qmin(l,r);
int mx = qmax(l,r);
int z;
if (l==0 and r==n-1) z=0;
else if (l==0) {
z=qmax(r+1,n-1);
}
else if (r==n-1) {
z=qmax(0,l-1);
}
else {
z=max(qmax(0,l-1),qmax(r+1,n-1));
}
double res = max((double)z,(double)(mx-mn)/2) + mn;
cout << res << "\n";
}
}