Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

scipianus's blog

By scipianus, 6 years ago, In English,

474A - Keyboard

This is an implementation problem, therefore most of the solution fit in the time limit. We can even save the keyboard in 3 strings and make a brute force search for each character to find its position and then print the left/right neighbour.

474B - Worms

There are two solutions:

  1. We can make partial sums ( sum i = a 1 + a 2 + ... + a i) and then make a binary search for each query q i to find the result j with the properties sum j - 1 < q i and sum j ≥ q i. This solution has the complexity O(n + m·log(n))

  2. We can precalculate the index of the pile for each worm and then answer for each query in O(1). This solution has the complexity O(n + m)

474C - Captain Marmot

For each 4 points we want to see if we can rotate them with 90 degrees such that we obtain a square. We can make a backtracking where we rotate each point 0, 1, 2 or 3 times and verify the figure obtained. If it's a square we update the minimal solution. Since we can rotate each point 0, 1, 2 or 3 times, for each regiment we have 44 configurations to check. So the final complexity is about O(n).

474D - Flowers

We can notate each string as a binary string, instead of red and white flowers. A string of this type is good only if every maximal contigous subsequence of "0" has the length divisible by k. We can make dynamic programming this way : nr i = the number of good strings of length i. If the i-th character is "1" then we can have any character before and if the i-th character is "0" we must have another k - 1 "0" characters before, so nr i = nr i - 1 + nr i - k for i ≥ k and nr i = 1 for i < k. Then we compute the partial sums ( sum i = nr 1 + nr 2 + ... + nr i) and for each query the result will be sum b - sum a - 1. This solution has the complexity O(maxVal + t), where maxVal is the maximum value of b i.

474E - Pillars

We have to find a substring i 1, i 2, ..., i k such that abs(h i j - h i j + 1) ≥ D for 1 ≤ j < k. Let's suppose that the values in h are smaller. We can make dynamic programming this way : best i = the maximal length of such a substring ending in the i-th position, best i = max(best j) + 1 with j < i and h j ≥ D + h i or h j ≤ h i - D. So we can easily search this maximum in a data structure, such as an segment tree or Fenwick tree. But those data structure must have the size of O(maxH) which can be 109. For our constraints we mantain the idea described above, but instead of going at some specific position in the data structure based on a value, we would normalize the values in h and binary search the new index where we should go for an update or a query in the data structure. Therefore, the data structure will have the size O(n). The complexity of this solution is O(n·log(n)).

474F - Ant colony

For each subsequence [L, R] we must find how many queens we have. A value is "queen" only if is the GCD of ( s L, s L + 1, ..., s R). Also, we must notice that the GCD of ( s L, s L + 1, ..., s R) can be only the minimum value from ( s L, s L + 1, ..., s R). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of ( s L, s L + 1, ..., s R) and if these two values are equal then we output the answer R - L + 1 - nrValues, where nrValues is the number of values in the subsequence equal to the GCD and the minimum value. The complexity of this solution is O(n·log(nlog(valMax) + t·log(nlog(valMax)), where valMax is the maximum value of s i.

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

Why the time complexity of pE is O(n·log(n)·log(n)) other than O(n·log(n))?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    +1. Scan the array->O(n) For each element: Do the binary search->O(logn) Get the maximum element from segtree->O(logn)

    In total:O(n(logn+logn))=O(nlogn)

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I couldn't understand what we're looking with binary search. Can you elaborate?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's what I thought since a segment tree with dynamic memory is perfect for the problem, but I guess the author's idea is simpler to come up with if you are not familiar with dynamic memory structures.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

in problem F nrVaues can be easily calculated in . Let's make pairs {number, occurrence in string}. Then we can do nrValue=upper_bound({x,r})-lower_bound({x,l}); So we don't even need to find min, only gcd.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But the gcd adds the additional log-factor to the complexity, no?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      Actually I'm not sure since gcd(a 1, a 2, ..., a n) works in not summary. Maybe you should not multiply but sum logs.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First time to know that upper_bound can make binary search on pairs , Thanks

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone please explain why and how does it work in finding number of occurrences of x in the range [l,r]?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For E as well you don't need extra log factor — use segment tree without normalization.

But those data structure must have the size of O(maxH)

You can implement segment tree so that it will have a O(N) size, no matter what is the range of the input values.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Could you explain to us this clearly because i can't imagine how to solve this problem ?

    i thought about nearly all the solution but got stuck on how to search in a segment tree whose maximum value should be 10^9 ?

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In C, it's faster to write (copy-paste) 4 cycles for(a[0] =0; a[0] < 4; a[0]++) than write a backtrack.

Also, my solution to checking if the figure is a square was: try all permutations of vertices and check if they're the vertices of a square in that order on the perimeter. No cases whatsoever and you can be easily sure that it works :D

Also, E: compress A[i], A[i] - D, A[i] + D, take 2 Fenwick trees (for maximum of interval [0, i] and [j, ∞]) and do the standard LIS algorithm.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain why my C soln failed?

    Thanks in advance.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are 2 main reasons: 1. Overflow (which I had :( ) -> hard to notice. 2. Wrong square checking.

»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Just because n = 4 doesn't make the complexity of problem C linear . If the problem was generalized to a regular polygon with n ≤ 20 sides, this wouldn't be possible in linear time. The complexity is exponential , and in this case n is relatively small.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Complexity of C problem is O(n*4^4)=O(256n)=O(n). For each quadruple we try every option.Evry point in this quadruple can be in 4 different position,that is 256 combinations.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what would n be in the case and why was 4 raised to the power of 4?

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        The complexity of C is O(4 p n), where p is the number of moles in one regiment (number of sides of the polygon) and n is the number of regiments (number of queries). For the problem, p = 4 is a constant, so O(4 p n) = O(44 n) = O(n) because coefficients are not included in big-O notation.

        You have mistaken n for the number of moles in one regiment instead.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, editorial says: "we can easily search this maximum in a data structure, such as an segment tree or Fenwick tree"

How to do this?

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem E can be solved using implicit segment tree 8119774

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me what's wrong with my solution for problem D. Here's the link > Link

__ When K = 1, it is 2^Length ! __ For any Other K, it works like the Fibonacci sequence !

Where am I going wrong ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    sum[b]-sum[a-1] can be negative

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it possible to solve pF without segment trees !if yes can someone provide few insights into it !

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sqrt-decomposition also works for given constraints.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, of course. Thanks a ton allllekssssa!

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for(int i=1;i<=100000;i++){ if(i==1) dp[1][0]=1; else dp[i][0] =( dp[i-1][0]+ dp[i-1][1] )%mod; if( i==k) dp[i][1]=1; else dp[i][1] =((i-k>=0)?(dp[i-k][0]+dp[i-k][1]):0 )%mod; update(i,dp[i][0]+dp[i][1]); }

        where dp[i][0]: number of ways so that the i length string end with Red and dp[i][1] : number of ways so that the i length string end with white

        the above solution is giving WA? can you explain sol

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain what exactly a good sequence is?? I'm not able to get the question correctly.Thanks

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain how to search maximum in Fenwik tree?

I used treap in this task.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In A, it is not even necessary to store three different arrays, as it is assured you are still hitting the keyboard, and will never hit [q, a, z] when d = R, and never [p, ;, /] when d = L. Therefore just looping through each of the n <= 100 characters on one array containing the entire keyboard works, as well.

On C, it is relatively easy to loop through the small number of vertices and find their rotations, but what criteria are there to calculate if the resulting figure is a square (I did not attempt solving for the reason, but I assumed tilted squares would be included)?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In C, for each possible rotation, I tried all permutations of the 4 points and checked if the lengths were equal, if the angles formed were 90 degrees and if the points were different from each other.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It might be easier to do the following: 1) calculate all 6 possible distances (or distance^2) 2) sort 3) square should have first four and last two distances equal

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second approach to Problem B, the time complexity seems to be O(sum+m) where sum is the number of all worms. By "precalculate the index of the pile for each worm", I think the author means using an array (of maximum size, 10^6) to remember the pile each worm is in.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/474/submission/8112838 This is my solution to 474B It shows wa on pretest 1. The code runs fine on my pc as well as ideone.com Can someone please help?? :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In some case there is no return in your function solve which will lead to unexcepted answer.Just change the loop condition (from<to) to (from<=to).

»
6 years ago, # |
Rev. 4   Vote: I like it +23 Vote: I do not like it

Problem : E -> http://codeforces.com/contest/474/submission/8122825

In this, he assumed that his solution sequence will not have any index i,j such that abs(i-j) > 300. Its pure fluke because he tried it before, assuming abs(i-j) <= 800. Both got Accepted. Is there a logic or just weak test cases?

I would also appreciate if someone can give detailed explanation of Problem:E or any link of tutorial because it's a new concept for me.

Thanks.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    No logic, just a weak test set. Countertest:

    100000 2
    1 2 2 2 2 ... 2 2 2 3
    
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks! Well can you provide some helpful links for similar problems (easier ones to get me started) ?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B i wrote the 1st solution and got time limit :| what's the problem?

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    Well, it is too slow... :D It is O(m * n). For every x in your solution you may have to look up to n values so it's O((number of x's) * n) = O(m * n). For every x you have to search for the first b[i] >= x with binary search or use lower_bound from stl http://www.cplusplus.com/reference/algorithm/lower_bound/ . Then it will be O(m * log(n)).

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

someone give proper explanation of which data structure and its implementation for finding max in problem E..

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

@sandyeep can u be more elaborate about the IMPLEMENTATION of st in the problem as the editorialist has not taken effort to explain his approach..

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code can pass the test data Your text to link here...

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in 471b how is the complexity O(n+m) if we precalculate the index of the pile of each worm??can u elaborate somewhat ??

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Any hint to get the rep of an element in a segment { l , r } !!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in the B i can't make it clear to me how have they used binary search?? anyone answer ASAP

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem D, could someone further explain how to derive the formula nr i  =  nr i  -  1  +  nr i  -  k for i  ≥  k? Thanks!

EDIT: Get it now!

If the i-th position is R, then there could be nr i - 1 possibilities, if the i-th position is W, we have to have k Ws, taking the last k positions, therefore nr i - k possibilities. Thus nr i  =  nr i  -  1  +  nr i  -  k in total.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For problem D Could you please explain .... why we have to do sumb - suma - 1.?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's called a cumulative sum trick, you can google it for more info

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain what's wrong with my formulation for problem 474D Flowers, f[I]=f[I-1]+I/k

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem_F

How I calculate nrValues efficiently .

I got TLE for this calculation .

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D: why k=1 is not special??

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please explain editorial of problem E-pillars broadly?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for Problem D.

nr[i] = nr[i-1] + nr[i-k], if i >= k...

nr[i] = nr[i-1], i < k..

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what do we need to calculate in problem D? I'm not getting what even the examples are indicating! Can anyone help?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    may be you got the solution. actually here between a and b we have to calculate the numbers of combination so he can eat the rose. we take simple example

    n=1 and k=1 possibilities= R,W only two // he can eat only in the group of k so may be he it 0 for white type or 1

    n=2 and k=1 possibilities=RR,RW,WR,WW only four // same here

    n=3 and k=1 possibilities=RRR,RRW,RWR,WRR,WWR,WRW,RWW,WWW only eight

    so in test case if inputs are a and b then we have to give all the sum between a and b

    input t=1 k=1 a=1 b=1 then we have to give answer all sum between 1 and 1 means only for length 1. answer=2 now i am taking another example so you can easily understand n=1 and k=3 possibilities=R only 1 // we can eat white flowers only in the group of k means here 3

    n=2 and k=3 possibilities= RR only 1 // we can eat white flowers only in the group of k means here 3

    n=3 and k=3 possibilities=RRR,WWW only 2 // we can eat white flowers only in the group of k means here 3

    n=4 and k=3 possibilities=RRRR,RWWW,WWWR only 3 // we can eat white flowers only in the group of k means here 3

    n=5 and k=3 possibilities=RRRRR,RRWWW,RWWWR,WWWRR, only 4 // we can eat white flowers only in the group of k means here 3

    input t=5 k=3 a=1 b=1 answer=1

    a=2 b=2 answer=1

    a=1 b=2 answer=2 // we have to give all the sum between 1 and 2 means all possibilities

    a=1 b=5 answer=11 //n=1->1, n=2->1, n=3->2, n=4->3, n=5->4

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello please someone here helpmeout in finding mistake in my code of Problem D I am getting wrong answers on some of the outputs[submission:51238549]

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the problem statement of the problem D.Flowers.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also trying to figure out the problem statement... I have no idea what a and b are supposed to represent. Intuition says red/white flowers numbers but examples don't seem to follow that ...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The answer to the problem will be the sum of ways in which the flowers can be eaten if total number of flowers to be eaten is a,a+1,a+2,a+3....b. Or you could say, final ans=NOW(a)+NOW(a+1)+NOW(a+2)+...NOW(b) where NOW stands for number of ways of eating the flowers when the given conditions are followed.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Used DP to solve problem D.....Still I'm getting TLE.....can anyone help please?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot figure out what is wrong in my solution for 474E Pillars. I have used 2BIT for prefix and suffix max queries. It would be very helpful if someone can find out where the problem is. My submission: https://codeforces.com/contest/474/submission/59685511

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Was anyone successful using method 1 (Binary Search) to solve 474B Worms. I am stuck with TLE.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Figured it out. Apparently i cannot delete comments on codeforces. Sorry

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, Can someone please explain why this is used... nri = nri - 1 + nri - k

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider eating the ith flower, if i >= k, then there can be two ways to do that(if i < k, then there is only one way to eat this number of flowers, i.e. eat all RED), either the ith flower is WHITE or it is RED. If the ith flower you ate is WHITE then you need to eat k — 1 more flowers hence result will depend on the ways to eat i — k flowers, but if the ith flower you ate is RED, then you need to find the ways to eat i — 1 flowers, thus the sum dp[i — 1] + dp[i — k].

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys I was working on problem D and deduced this formula: f(i)=1+(t*(i+1))%m — ((k*t*(t+1))/2)%m; Here t is [i/k]. Idk why but this fails on test case 3. Here f(i) denotes the answer for i'th length. Here is the link to my submission. Please look into this if you can as I saw no comments/solutions using this formula!!!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hey, the derived formula is wrong as this formula considers only cases where all whites are together ,

    i.e. if k=2, it considers only cases like RWWWWR, WWWWRR etc

    and not the cases RWWRWW

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F,we dont require to find the RMQ ,the answer could be obtained just by finding the gcd of the range i.e [l,r] and the number of elements in the range [l,r] where the element is equal to the gcd of range [l,r] and the obtain the result as r-l+1+ #of elements which satisfy the above property. Here is my code 75179979

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me out with my solution for B. My binary search results in TLE and I cant figure out why. https://codeforces.com/contest/474/submission/77444439

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me what is wrong in my code for problem D. Here is the link to my solution 80443947

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You prolly making the same mistake as I was. It is possible to have a pair (l — 1, r), such that r > l but dp[r] < dp[l — 1]. This is because we are storing dp* as MOD 1e9 + 7. So, dp[r] — dp[l — 1] will be negative, C++ handles negative mods in a different that you would expect, negative mods are kept negative, so -1 MOD 5 isn't converted to 4. So you need to do (dp[r] — dp[l — 1] + MOD) % MOD.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can refer this

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

can anyone tell me what is wrong in my approach

ll dp[100001][2]; ll helper(ll n, ll k, bool flag){ if(n == 0) return 1;

if(n < 0) return 0;

if(dp[n][flag] != -1) return dp[n][flag];

ll ans1 = 0;
ll ans2 = 0;
ans1 = (ans1 + helper(n - 1, k, 0))%mod;
if(!flag )
    ans2 =(ans2 + helper(n - k, k, 1))%mod;

return dp[n][flag] = (ans1%mod + ans2%mod)%mod;

}

it is giving me answer 4 when a = 4 and b = 4

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell me wr i m worng in this code 474F ant colony

https://codeforces.com/contest/474/submission/84365772

    #include<bits/stdc++.h>
    #define fr(i,n) for (int i = 0; i < n; i++)
    #define pb push_back
    #define mt make_tuple
    #define ff first
    #define ss second
    #define ii pair<int,int>
    #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

    #define vi vector<int>
    #define vii vector<ii>
    #define ll long long int
    #define ull unsigned long long int
    #define di(a,b) sqrt(a*a+b*b)
    #define INF 1e17
    #define endl '\n'
    const double PI = 3.141592653589793238460;
    typedef std::complex<double> Complex;
    //typedef pair<int, int> pi;
    typedef std::valarray<Complex> CArray;
    using namespace std;


    pair<pair<int,int >,int > combine(pair<pair<int,int >,int >p1,pair<pair<int,int >,int >p2)
    {  
    if(p1.ss==0){return p2;}
       if(p2.ss==0){return p1;}

       if((p1.ff.ff==0 && p2.ff.ff==0) || (p1.ff.ss%p2.ss && p1.ff.ff==0) || (p2.ff.ss%p1.ss && p2.ff.ff==0)){  return {{0,__gcd(p1.ff.ss,p2.ff.ss)},min(p1.ss,p2.ss)};}
       if(p1.ff.ff==0 )
         {
          return {{p2.ff.ff,p2.ff.ss},p2.ss};
         }
       if(p2.ff.ff==0 )
         {
          return {{p1.ff.ff,p1.ff.ss},p1.ss};

         }
       if(p1.ss==p2.ss){ return {{p1.ff.ff+p2.ff.ff,p1.ss},p1.ss};}
       if((max(p1.ss,p2.ss))%(min(p1.ss,p2.ss))==0){int x1;if(p1.ss<p2.ss)x1=p1.ff.ff;else x1=p2.ff.ff;  return {{x1,min(p1.ss,p2.ss)},min(p1.ss,p2.ss)}; }
       else{ return {{0,1},min(p1.ss,p2.ss)};}
    }

void build(pair<pair<int,int >,int> t[],int ar[],int tl,int tr,int v)
{

    if(tl==tr){t[v]={{1,ar[tl]},ar[tl]}; }  
    else
    {
       int mid=(tl+tr)/2;
       build(t,ar,tl,mid,2*v);
       build(t,ar,mid+1,tr,2*v+1);
       t[v]=combine(t[2*v],t[2*v+1]);


    }
}

pair<pair<int,int >,int > get(pair<pair<int,int >,int > t[],int ar[],int tl,int tr,int v,int l,int r)
{
    if(l>r)return {{0,0},0};
    if(tl==l && tr==r){return t[v];  }  
    int mid=(tl+tr)/2;
    pair<pair<int,int >,int> pa=combine(get(t,ar,tl,mid,2*v,l,min(r,mid)),get(t,ar,mid+1,tr,2*v+1,max(l,mid+1),r));

       return pa;}


    int main()
    {  
int n,m,a,b,c;
cin>>n;
int s[n];
fr(i,n)cin>>s[i];
pair<pair<int,int >,int > t[4*n+5];
build(t,s,0,n-1,1);


int t1;
cin>>t1;
while(t1--)
{
    cin>>a>>b;
    a--;b--;
    pair<pair<int,int >,int >pt=get(t,s,0,n-1,1,a,b);
    cout<<(b-a+1-pt.ff.ff)<<endl;
}


       return 0;
    }