In the year (say $$$y$$$) we celebrate $$$(y-1946)^{th}$$$ independence day

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout << n-1946 << endl;
    }
}

Anmol starts at the origin $$$(0,0)$$$ initially. Let his position after $$$k$$$ $$$(k < n)$$$ moves be $$$(x,y)$$$ and his final position be $$$(X,Y)$$$ . Since his distance from origin always increases, exactly one of $$$|x|$$$ or $$$|y|$$$ increases by $$$1$$$ unit after every move. Initially his distance from $$$(0,0) = 0$$$. Since, his distance increases by exactly $$$1$$$ unit after every move, after $$$n$$$ moves, his distance from $$$(0,0) = n$$$, i.e. his coordinates of his final position follows the relation $$$|X| + |Y| = n$$$. It can be seen that this is a square centred at the origin. The number of points in such a square $$$= 4 \cdot n$$$. ($$$n-1$$$ in every quadrant and $$$4$$$ on the coordinate axes).

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout << 4*n << endl;
    }
}

The seats that can be occupied by the teams are seat 1, (1+2), (1+2+3) and so on. We can use a loop and check if the seat is available, updating the seat accordingly inside the loop, and incrementing the answer by one if the current seat number is less than or equal to n, otherwise, break out of the loop.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int capacity=0, i=0;
        while(capacity+(i+1) <= n)
        {
            i++;
            capacity += i;
        }
        cout << i << endl;
    }
}

The question states that we have a function which generates the newer terms of the sequence.

Now if n is odd the next term in sequence is 3*n+3. Now note that this new term is for sure a multiple of 3.

If n is even we see that next term is n/2. This can only reduce a number of the form 2k to k.

So if k has any prime number other than 2 as it's factor then the new term in the sequence gets a multiple of 3 which will never be destroyed.

By destroyed I mean that the function n to n/2 destroys powers of 2. But if power of 3 is present or in general any other prime then it doesn't vanish out here.

So for powers of 2 this is a terminating sequence. For others it non terminating.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        while(n%2==0)
            n/=2;
            
        if(n == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

If string is palindrome, we know answer is $$$1$$$.

If string is not palindrome, then you can notice that string will consist characters $$$a$$$ and $$$b$$$ both.

We will choose a subsequence such that all $$$a$$$ are present in it. This subsequence is a palindrome.

What will be left after removal of all $$$a$$$ will be all $$$b$$$. In next move, we choose whole string. So we can do it in $$$2$$$ moves.

#include <bits/stdc++.h>
using namespace std;

bool ispal(string s)
{
    for(int i=0; i<s.size()/2; i++)
    {
        if(s[i]!=s[s.size()-1-i])
            return false;
    }
    return true;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        if(ispal(s))
            cout << "1" << endl;        //remove the whole string in a single move
        else
            cout << "2" << endl;        //remove the subsequence with all a's first, then remove the subsequence with all b's
    }
}

Here the main observation is that if Abhinav needs $$$k$$$ coins, where $$$k$$$ is even, he needs only $$$k/2$$$ coins, and by using his mysterious power, he can get another $$$k/2$$$ coins. Similarly, if $$$k$$$ is odd, Abhinav needs $$$\frac{p-1}{2}$$$ coins which, by using his mysterious power, becomes $$$p-1$$$ coins, then Abhinav can take $$$1$$$ coin as a loan from the bank. This way, Abhinav can achieve the minimum number of coins he needs to take as a loan from the bank.

To achieve this, we will go in the reverse direction, i.e. at each step:

• We will check if $$$k$$$ is odd, then we will add $$$1$$$ in our answer; else, we won't add anything to the answer.
• We will divide current $$$k$$$ by $$$2$$$.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n, ans=0;
        cin>>n;
        int n1=n;
        while(n)            //count number of set bits in n
        {
            ans += n%2;
            n /= 2;
        }
        cout << ans << endl;
    }
}

The idea in this problem is to keep only one red chair from a contiguous subsegment of the arrangement containing $$$\geq$$$ 1 red chair, while the blue chairs will always be present in the final arrangement. Note that the chairs are arranged in circular order, so if $$$s[n-1]$$$ and $$$s[0]$$$ both are $$$R$$$, then they'll form such a contiguous subsegment.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        stack<char> st;
        string s;
        cin>>s;
        st.push(s[0]);
        for(int i=1;i<n;i++)
        {
            if(s[i]=='R')
            {
                if(st.top()!='R') st.push(s[i]);
            }
            else st.push(s[i]);
        }
        if(s[0]=='R'&&st.top()=='R'&&st.size()>1)cout<<st.size()-1<<endl;
        else cout<<st.size()<<endl;
    }
}

Assume the initial line is a queue with people indexed from $$$1$$$ to $$$N$$$. If a person gets a $$$good$$$ guava then remove him from the queue, if he gets a $$$bad$$$ one remove him from the front of the queue and put him at the back. We maintain an array for the time at which each index leaves the queue (he gets a $$$good$$$ guava), which is essentially the index of the guava he gets in the given string of $$$good$$$ ($$$G$$$) and $$$bad$$$ ($$$B$$$) guavas. Essentially we simulate the process of the queue itself starting from the first guava and coming out if the guavas get over or if the queue becomes empty (all the people are served).

#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int m,n;
    cin>>m>>n;
    string guavas;
    cin>>guavas;

    int query_count; 
    cin>>query_count;
    int arr[query_count];
    for(int i=0; i<query_count; i++)
        cin>>arr[i];
    
    queue<int> q;
    for(int i=0; i<n; i++)
    {
        q.push(i);
    }

    vector<int> b(n,-1);
    for(int i=0;i<=m-1;i++)
    {
        if(q.empty())
        {
            break;
        }
        if(guavas[i]=='G')
        {
            b[q.front()]=i+1;
            q.pop();
        }
        else
        {
            q.push(q.front());
            q.pop();
        }
    }

    for(int i=0;i<=query_count-1;i++)
    {
        cout<<b[arr[i]-1]<<endl;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

It is obvious that $$$k$$$ must be $$$\leq n$$$, since sums of digits (i.e. $$$k_1, k_2, k_3$$$) must be non-negative. So, $$$k\leq 10^9$$$. Now, \begin{itemize} \item $$$max(k_1) = 9 \cdot 9 = 81$$$, for $$$k=999999999$$$ \item $$$max(k_2) = 7+9 = 16$$$, when $$$k_1 = 79$$$ \item $$$max(k_3) = 9$$$, when $$$k_2 = 9$$$ \end{itemize} Therefore, $$$max(k_1+k_2+k_3)=106$$$. This means it's enough to search just in the 106-spanning left neighbourhood of the number $$$n$$$, viz. $$$[max(0, n-106), n]$$$ (max of zero and $$$n-106$$$ to be taken, since $$$n$$$ may be smaller than 106, and we don't want out of bound solutions).

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()

const ll mod=1000000007;
const ll N=200005;

ll func(ll x)
{
    ll val=0;
    while(x)
    {
        val+=x%10;
        x/=10;
    }
    return val;
}

void solv()
{
    ll n;
    cin>>n;
    vector<ll> ans_vec;
    for(ll i=max(0ll,n-100); i<=n; i++)
    {
        ll f = func(i);
        ll ff = func(f);
        ll fff = func(ff);
        if(i+f+ff+fff == n)
            ans_vec.push_back(i);
    }
    
    cout << sz(ans_vec) << endl;

    if(sz(ans_vec))
    {
        for(ll i=0; i<sz(ans_vec); i++)
            cout << ans_vec[i] << " ";
        cout << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}

Suppose the number $$$A$$$ is in base $$$k$$$. So, in decimal base, it will have a value of $$$(A){10}=\sum{i=1}^{n} a_{n-i} \cdot k^{i-1}$$$. Now, according to the question's requirement:

$$$(k-1)$$$ divides $$$\sum_{i=1}^{n} a_{n-i} \cdot k^{i-1}$$$

$$$\Rightarrow$$$ $$$m$$$ divides $$$\sum_{i=1}^{n} a_{n-i} \cdot(1+m)^{i-1}$$$, where $$$m=(k-1)$$$

$$$\Rightarrow m$$$ divides $$$\sum_{i=1}^n a_{n-i}$$$

$$$\Rightarrow m$$$ divides $$$\sum_{i=1}^n a_{i}$$$, i.e. the sum of the digits of $$$A$$$

Also, such $$$k$$$ must be $$$>max{\forall a_i}$$$, else the digits won't be defined. So, we just have to store all the divisors (i.e. all such $$$m$$$'s) of $$$S = \sum_{i=1}^n a_{i}$$$ which are $$$\geq max{\forall a_i}$$$. This can be done in $$$O(\sqrt{S})$$$ time-complexity. Even in the worst case, it will undergo at most $$$\sim 10^5$$$ iterations, taking no more $$$1$$$ seconds to execute.

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

void solve()
{
    int n;
    cin >> n;
    int a[n];
    int64_t sum = 0;
    int m = INT_MIN;
    for(int i = 0; i<n; i++)
    {
        cin >> a[i];
        sum += a[i];
        m = max(m,a[i]);
    }
    set<int> s;
    int count = 0;
    for(int i = 1; i*i<=sum; i++)
    {
        if(sum % i == 0)
        {
            if(i == sum/i)
            {
                if(i >= m)
                    s.insert(i+1);
            }
            else
            {
                if(i >= m)
                    s.insert(i+1);
                if(sum/i >= m)
                    s.insert(sum/i+1);
            }
        }
    }
    cout << s.size() << "\n";
    for(auto &val : s) cout << val << " ";
    cout << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

Find the maximum possible value of index 'i' (i<x) according to the given condition and subtract this index from the rest to get the new indices after it's rotation

Obviously if there is no one in front of Jigyasa with height greater than or equal to $$$k$$$ in the queue then the answer must be 0.

Let us consider the more interesting case when there exists atleast one $$$i < x$$$ such that $$$h_i \geq k$$$. Let at any time the state of the queue is such that the most recent removal operation was done on the person who's index in the original queue was $$$pos$$$ (Consider zero indexing). Hence, the $$$i^{th}$$$ person in the original queue has an effective position of $$$i - pos$$$ in the new queue (Assuming $$$i > pos$$$ and 0-based indexing). Now the condition required to be valid to apply a Removal operation on index $$$i$$$ would be $$$x - i \geq i - pos$$$.

We could solve the following problem by maintaining two pointers, one pointing to the last index that required a removal operation and one pointing to a possible future candidate for the removal operation. Let us call these variables $$$pos$$$ and $$$curr$$$ respectively. We can initialise $$$pos$$$ and $$$curr$$$ each to -1 and iterate over all i from 0 to $$$x$$$, updating $$$curr = i$$$ everytime we find an $$$i$$$ that satisfies the given conditions (i.e. $$$h_i >= k$$$ and $$$x - i >= i - pos$$$). and updating $$$pos = curr$$$, $$$curr = i$$$ and incrementing our total counter everytime we find that $$$h_i >= k$$$ but $$$x - i < i - pos$$$.

We can detect whether an answer exists or not by running an initial for loop which checks the condition $$$x - i >= i - pos$$$ for all $$$i$$$ from 0 to $$$x - 1$$$ such that $$$h_i >= k$$$. If this isn't satisfied then no such sequence of operations exist.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()

const ll mod=1000000007;
const ll N=200005;

ll solv()
{
    ll n,k,x;
    cin>>n>>k>>x;
    vector<ll> a(n+1);
    vector<ll> b;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i];
        if(a[i]>=k)
            b.push_back(i); 
    }

    ll lftmost_k = b[0];
    ll lft_el = 1;
    ll mov=0;
    while(1)
    {
        lftmost_k = *lower_bound(b.begin(),b.end(),lft_el);
        if(lftmost_k == x)
            return mov;

        /*      y - lft <= x - y - 1
                2*y     <= (x + lft - 1) 
                y       <= (x + lft -1)/2        */

        ll max_allowed = (lft_el+x-1)/2;
        auto itr = upper_bound(b.begin(),b.end(),max_allowed);
        if(itr == b.begin())
            return -1;
        itr--;
        if(*itr < lft_el)
            return -1; 
        
        mov++;
        lft_el = *itr + 1; 
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        cout << solv() << endl;
    }
    return 0;
}

Let's consider the array $$$A$$$ to have elements $$$a_1, a_2, \ldots, a_n$$$. Let's call the GCD of all elements in the array to be $$$gcd$$$.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()

const ll mod=1000000007;
const ll N=200005;

ll solv()
{
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
    }

    //Corner case
    if(n==1)
        return 0;
    if(n==2)
    {
        if(a[0]==a[1])
            return 0;
        else
            return -1;
    }

    //Evaluating GCD of array & freq[GCD]
    ll gcd = a[0];
    for(ll i=1; i<n; i++)
    {
        gcd = __gcd(gcd, a[i]);
    }
    ll gcd_count = 0;
    for(ll i=0; i<n; i++)
    {
        if(a[i] == gcd)
            gcd_count++;
    }

    if(gcd_count == n)      // All elements are equal already
    {
        return 0;
    }
    else if(gcd_count > 1)  // > 1 occurence of gcd in array
    {
        return 1;
    }
    else if(gcd_count == 1) // 1 occurence; check if GCD of remaining elements = gcd
    {
        ll rest_gcd;
        if(a[0] == gcd)
            rest_gcd = a[1];
        else
            rest_gcd = a[0];
        
        for(ll i=0; i<n; i++)
        {
            if(a[i] != gcd)
            {
                rest_gcd = __gcd(rest_gcd, a[i]);
            }
        }

        if(rest_gcd == gcd)
            return 1;
        else
            return 2;
    }

    //Check if we can find n-1 size subsequence such that their GCD = array gcd
    vector<ll> pref_gcd(n,a[0]);
    for(ll i=1; i<n; i++)
        pref_gcd[i] = __gcd(pref_gcd[i-1],a[i]);
    
    vector<ll> suff_gcd(n,a[n-1]);
    for(ll i=n-2; i>=0; i--)
        suff_gcd[i] = __gcd(suff_gcd[i+1],a[i]);
    
    bool flag = false;  //flag = true if we can find n-1 elements in the array such that GCD of those elements = gcd
    if(pref_gcd[n-2]==gcd || suff_gcd[1]==gcd)
        flag = true;
    
    for(ll i=1; i<n-1; i++)
    {
        if(__gcd(pref_gcd[i-1],suff_gcd[i+1])==gcd)
        {
            flag = true;
            break;
        }
    }

    if(flag)
        return 2;
    else
        return 3;   
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        cout << solv() << endl;
    }
    return 0;
}

We can process the tower sequence from left to right. When we are at the $$$i^{th}$$$ tower, we'll have the optimal sequence of moves from towers $$$1$$$ to $$$i-1$$$.

Let's call the move $$$[$$$tower $$$i-1$$$ to tower $$$i]$$$ to be $$$m_1$$$. Now, we check if we can merge the latest move (move on top of stack) with $$$m_1$$$. If that works, we form the merged move $$$m_2$$$ and pop the topmost move from the stack. We repeat this process until we can't do a merge.

Once we can't do a merge, we'll have the optimal sequence of moves from towers $$$1$$$ to $$$i$$$. We can now move on to process tower $$$i+1$$$.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()

const ll mod=1000000007;
const ll N=200005;

bool collision(vector<ll> &a, ll i, ll j, ll k)
{
    if((a[k]-a[i])*(j-i) >= (a[j]-a[i])*(k-i))
        return false;
    return true;
}

double slope(vector<ll> &a, ll i, ll j)
{
    return fabs((double)(a[j]-a[i])/(j-i));
}

void solv()
{
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
    }

    vector<ll> s;       //serves as a stack here
    s.push_back(0);
    s.push_back(1);
    for(ll i=2; i<n; i++)
    {
        while(s.size()>=2)
        {
            if(!collision(a,s[s.size()-2],s.back(),i))
            {
                s.pop_back();
            }
            else    
                break;
        }
        s.push_back(i);
    }
    double ans = slope(a,s[0],s[1]);
    for(ll i=2; i<s.size(); i++)
        ans = max(ans, slope(a, s[i], s[i-1]));
    
    cout << fixed << setprecision(7) << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}

What happens when you start with column with height $$$x$$$?

If frequency of height $$$x$$$ is $$$freq[x]$$$ then how many moves can be done?

If we start on a column with height $$$x$$$ then all other columns' height will decrease by 1. So for us to do next "Jump" move, there should be another column of height $$$x$$$ so that it can become $$$x-1$$$ after doing "Attack" move.

Let $$$freq[x]$$$ store initial frequency of columns with height $$$x$$$. So following happens if you start on column with height $$$x$$$,

• "Attack" — Now there are $$$freq[x]-1$$$ columns left with height $$$x-1$$$
• "Jump" — You can jump to any 1 of them
• "Attack" — Now there are $$$freq[x]-2$$$ columns left with height $$$x-2$$$
• ...

Crash can initially jump to any column, so we will calculate total Wumpa fruits collected for each initial column and maximum of those would be the answer.

LessCnt and LessSum can be counted in one iteration of the frequency array similar to prefix sum. And we can get number of fruits collected for each initial column in O(1). So total time complexity is O(10000) per test case.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()

const ll mod=1000000007;
const ll N=200005;

void solv()
{
    ll n;
    cin>>n;
    vector<ll> h(n), f(10001), cum_cnt(10001), cum_sum(10001);
    ll mini=mod;
    for(int i=0; i<n; i++)
    {
        cin>>h[i];
        f[h[i]]++;
        mini = min(mini, h[i]);
    }

    if(n==1)        // Corner case
    {
        cout << 0 << endl;
        return;
    }

    for(int i=1;i<=10000;i++)
    {
        cum_sum[i]=cum_sum[i-1]+f[i]*i;     //cum_sum[i] = sum of all elements <= i
        cum_cnt[i]=cum_cnt[i-1]+f[i];       //cum_cnt[i] = number of elements <= i
    }
    
    ll ans=0;
    for(int i=0;i<=10000;i++)
    {
        if(f[i]==0) continue;

        ll temp=0, mov=0;               //mov = number of moves we can do if we start on a crate of height i
        if((i > f[i]) || (i==f[i] && i==mini))
        {   
            mov = f[i];
            temp += cum_sum[mov];
            temp += (n-cum_cnt[mov])*mov;
            temp -= f[i];
        }
        else
        {
            mov = i+1;
            temp += cum_sum[mov];
            temp += (n-cum_cnt[mov])*mov;
        }
        ans = max(ans, temp);
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}

First crucial observation we can make is that since we are allowed to have negative money and negative position, we can always buy or sell a share on all days.

For any particular query let's say day i and price p, we can buy all the shares sold at a price lower than p and sell all the shares sold at a price higher than p till day i.

Let us say we are able to calculate the following quantities for every possible query

• $$$x_1$$$ — number of shares sold at a price lower than p till day i
• $$$x_2$$$ — sum of prices of all shares sold a price lower than p till day i
• $$$x_3$$$ — total sum of prices of all shares sold till day i

Thus we know,

• total number of shares sold till day i are i,
• $$$i-x_1$$$ shares would be sold at a price higher than or equal to p till day i (considering the price equal to p case here)
• $$$x_3-x_2$$$ would be the sum of the prices of all the shares sold till day i

So total profit that we would have is, (till day i)

= (Sum of prices of shares sold — Price at we will buy shares sold from IT dept * Number of Shares sold) + (Price at we will sell shares bought from IT dept * Number of Shares bought — Sum of prices of shares bought)

= $$$(x_3-x_2-p*(i-x_1)) + (p*x_1-x_2)$$$

Now all that is left to be done is calculating the values $$$x_1$$$, $$$x_2$$$ and $$$x_3$$$ for each query.

We can update the process day by day and answer the queries for that particular date. For this we can sort all the queries and answer the queries after every day is over.

To find $$$x_3$$$ is simple, we store a variable and increment the value of the variable with the value of the share that day

For computing $$$x_1$$$, we can use an ordered multiset. Every day we will insert the value of the current share in the multiset. Then for all the queries that particular day we will figure out the number of items in the list smaller than the given value.

For computing $$$x_2$$$, we can a segment tree. Let's say we had smaller constraints such that $$$p_i$$$ was small (~2e5). Then we could have considered a segment tree over the prices of the stocks. And once we get a stock with price $$$p_i$$$ on day i, we increment the $$$p_i^{th}$$$ index in the segment tree by $$$p_i$$$. Then while answering a query we can take the sum of the all the indices from 0 to $$$p_i$$$ in the segment tree and this will give us the sum of all the elements smaller than p.

But unfortunately, $$$p_i$$$ can go up to 1e9. Thus we cannot directly use such an array. But instead we can use a standard technique of compressing co-ordinates. Since we can have at max 2e5 distinct values for the stock prices, since we only have at max 2e5 days, we can map each of the distinct price of the stocks to a smaller value (say by sorting the stock vector, applying the std::unique function and mapping each of these distinct values to its index instead). Thus for each query, first we can check the stock price just smaller than price p using the ordered set that we already made earlier. Now this price will be mapped to some value $$$m_{p_i}$$$ as described earlier. Then calculating the sum from index i to index $$$m_{p_i}$$$ will give us $$$x_3$$$.

Thus we can calculate the total profit.

#include<bits/stdc++.h>

using namespace std;
using namespace chrono;

#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define precision(a) {cout << setprecision(a) << fixed;}

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<ld> vld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> si;
typedef set<ll> sll;
typedef set<pll> spll;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpll;
typedef tuple<ll,ll,ll> tll;
typedef vector<tll> vtll;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;
typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

ll t[800000]={0};
void build(ll a[], ll v, ll tl, ll tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        ll tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

ll sum(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    ll tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];
    }
}

void solve() 
{
	ll n;
	cin>>n;
	
	ll a[n];
	sll s;
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];
		s.insert(a[i]);
	}
	s.insert(0);

	mll ptoi, itop;
	ll c=0;
	for(auto i:s)
	{
		ptoi[i]=c;
		itop[c]=i;
		c++;
	}

	ll arr[c]={0};
	build(arr,1,0,c-1);

	ll q;
	cin>>q;

	pair<pll,ll> pq[q];
	for(ll i=0;i<q;i++)
	{
		cin>>pq[i].ff.ff>>pq[i].ff.ss;
		pq[i].ff.ff--;
		pq[i].ss=i;
	}
	sort(pq,pq+q);

	ll ans[q]={0};
	ordered_set prices;
	mll cnt;
	ll sumsofar=0;
	ll cntsofar=0;
	ll l=0;
	for(ll i=0;i<q;i++)
	{
		for(int j=l;j<=pq[i].ff.ff;j++)
		{
			prices.insert({a[j],cnt[a[j]]});
			cnt[a[j]]++;
			sumsofar+=a[j];
			cntsofar++;
			update(1,0,c-1,ptoi[a[j]],cnt[a[j]]*a[j]);
		}
		l=pq[i].ff.ff+1;

		ll price = pq[i].ff.ss;
		auto it = s.upper_bound(price);

		it--;
		ll ind = ptoi[*it];

		ll sumless = sum(1,0,c-1,0,ind);
		ll summore = sumsofar-sumless;

		ll cntless = prices.order_of_key({*it,1e9});
		ll cntmore = cntsofar - cntless;

		ans[pq[i].ss] = -sumless + cntless*price + summore - cntmore*price;
	}

	for(ll i=0;i<q;i++)
	{
		cout<<ans[i]<<"\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	solve();
}