# TLE in Binary Search Problem

The question:

Two people, A and B are playing a game. They have infinite stones. A starts the game and puts a1 stones in a stack. Then B adds a2 stones to the stack. A continues by adding a3 stones. This goes on till their friend, C enters and decides to show his intelligence and impress everyone by choosing a stone from top at random(He doesn’t remove this stone) and then tell whose stone it was. He does this q times. Output whose stone it was (A or B) and help C impress his friends with correct answers.
INPUT FORMAT

• The first line of the input contains a single integer n denoting the number of turns.
• Next line contains n space-separated integers denoting the stones added at each turn.
• Next line contains a single integer q denoting the number of queries.
• q lines follow:each of these lines contains the value of x denoting the position of the stone from the top.

OUTPUT FORMAT

For each query, print A or B.
Constraints:
1<= n <= 10^6
1<= q <= 10^6
0<= a-i <= 10^3
1<= x <= sum(a-i+ a-1 + a-2 + a-3 + a-4 …)

MY approach is to get an opposite order prefix sum array. Then perform a binary search on it.
But I am stuck.
Code:

``````#include<bits/stdc++.h>
using namespace std;
int main(){
long long int n;
scanf("%lld",&n);
int arr[n];
//arr=0;
for(long long int i=0;i<n;i++){
int temp;
scanf("%d",&temp);
arr[i]=temp;
}

int sum[n];
sum[n-1] = arr[n-1];

for(long long int i= n-2;i>=0;i--)
sum[i] = sum[i+1] + arr[i];
long long int q;
scanf("%lld",&q);

for(long long int y=0;y<q;y++){
int x;
scanf("%d",&x);
long long int l=0,r=n-1;
long long int ans = -1;
while(l<=r){
int mid = l =((r-l)/2);
if(arr[mid]>=x){
if(arr[mid-1]>=x)
r = mid-1;
else
ans = mid;
break;
}
else
l = mid+1;
}
if(ans%2==0)
printf("A\n");
else
printf("B\n");

}
}``````