Gazda Srbi šljiva nikad dosta i on redovno odlazi do pijace u susednom selu da razgleda nove sadnice za iste. Predstavljalo mu je problem to što je jako udaljena, međutim nedavno se otvorila nova pijaca u blizini i on je rešio da svakog jutra prošeta do nje ne bi li kupio nove sadnice za svoj šljivik.

Novootvorenu pijacu čini N tezgi koje se nalaze u redu jedna do druge. Na svakoj tezgi je moguće pronaći sadnice zajedno sa cenom za iste. Gazda Srba krene u obilazak počevši od neke tezge L i prođe redom svaku tezgu zaključno sa tezgom R, dok se zaustavlja samo na onim gde cena nije manja od A (jer zna da tog dana nisu kvalitetne) i na onim gde cena nije veća od B (jer su mu preskupe).

Gazda Srba uvek voli da isplanira ostatak dana, a dodatni problem mu predstavljaju cene koje variraju iz dana u dan, pa vas moli da mu napišete program koji bilo kada može odrediti broj tezgi na kojima će se zadržati.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke pijaca.in.) U prvom redu ulazne datoteke se nalazi N (1 ≤ N ≤ 50.000), broj tezgi na pijaci. U narednom redu se nalazi niz X (1 ≤ N_i ≤ 10⁹) od N brojeva koji predstavljalju početne cene sadnica na pijaci. Zatim, u sledećoj liniji, sledi Q (1 ≤ Q ≤ 50.000), broj upita koje trebate da odradite, i na kraju Q linija koje ih opisuju, oblika:
"1 L R A B - koji traži od vas da ispišete koliko ima tezgi od L do R (1 ≤ L ≤ R ≤ N) sa cenom sadnica između A i B (1 ≤ A, B ≤ 10⁹), uključujući A i B. "2 I J- u kojem se navodi da je nova cena sadnica na tezgi sa indeksom I (1 ≤ I ≤ N) jedanka J (1 ≤ J ≤ 10⁹).

Izlaz.

(Izlazni podaci se ispisuju u datoteku pijaca.out) Za svaki upit tipa 1 redom iz ulaza u posebnoj liniji ispišite traženi broj tezgi.

Primer 1.

6
3 2 1 2 5 5
3
1 2 5 2 3
2 3 2
1 2 6 2 3

2
3

Objašnjenje.Odgovor na prvi upit je 2 jer se gazda Srba na svom putu zaustavlja kod tezgi 2 i 4, dok je odgovor na naredni upit tipa 1 jednak 3 jer je cena sadnice na tezgi broj 3 u međuvremenu poskupela na 2 i njegov naredni obilazak pijace će upotpuniti i ova tezga.

Napomena.
U 40% test primera, neće biti upita drugog tipa. U ovim primerima je Q neparno, a tamo gde ima i upita drugog tipa je Q parno.

#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;

#define INF 2123456789

const int MaxN = 100005;

int a[MaxN], s[MaxN];
int n, q;

int upperBound(int left, int right, int x){
    while (left < right){
        int mid = (left + right) / 2;

        if (s[mid] <= x)
            left = mid + 1;
        else
            right = mid;
    }

    return s[left] > x ? left : left + 1;
}

int lowerBound(int left, int right, int x){
    while (left < right){
        int mid = (left + right) / 2;

        if (s[mid] < x)
            left = mid + 1;
        else
            right = mid;
    }

    return s[left] >= x ? left : left + 1;
}

int main(){
    FILE *fin = fopen("pijaca.in", "r");
    FILE *fout = fopen("pijaca.out", "w");

    fscanf(fin, "%d", &n);
    for (int i = 1; i <= n; i++){
        fscanf(fin, "%d", a+i);
        s[i] = a[i];
    }

    int k = 1;
    for (; k*k < n; k++);

    for (int i = n+1; i <= k*k; i++) a[i] = s[i] = INF;
    n = k*k;

    for (int i = 1; i <= k; i++) sort(s + (i - 1) * k + 1, s + i * k + 1);

    fscanf(fin, "%d", &q);
    while (q--){
        int command; fscanf(fin, "%d", &command);

        if (command == 1){
            int left, right, low, high; fscanf(fin, "%d%d%d%d", &left, &right, &low, &high);

            int sol = 0;
            while (left <= right && right % k){
                sol += low <= a[right] && a[right] <= high;
                right--;
            }

            while (left <= right && left % k != 1){
                sol += low <= a[left] && a[left] <= high;
                left++;
            }

            while (left <= right){
                int upper = upperBound(right - k + 1, right, high);
                int lower = lowerBound(right - k + 1, right, low);
                //int upper = (int)(upper_bound(s + right - k + 1, s + right + 1, high) - s);
                //int lower = (int)(lower_bound(s + right - k + 1, s + right + 1, low) - s);

                sol += upper - lower;
                right -= k;
            }

            fprintf(fout, "%d\n", sol);
        }
        else {
            int idx, num; fscanf(fin, "%d%d", &idx, &num);
            int left = idx - (idx - 1) % k, right = left + k - 1;

            int tmp = a[idx];

            a[idx] = num;
            idx = lowerBound(left, right, tmp);
            //idx = (int)(lower_bound(s + left, s + right + 1, tmp) - s);
            s[idx] = num;

            while (left < idx && s[idx-1] > s[idx]){
                int p = s[idx-1]; s[idx-1] = s[idx]; s[idx] = p;
                idx--;
            }

            while (idx < right && s[idx] > s[idx+1]){
                int p = s[idx]; s[idx] = s[idx+1]; s[idx+1] = p;
                idx++;
            }
        }
    }

    fclose(fin); fclose(fout);
    return 0;
}