Olkoon A taulukko. Tehtävänäsi on vastata kyselyihin, missä annettuna L ja R, sinun pitää palauttaa pienin arvo A[ i ] kaikkien L \leq i \leq R yli.

Syöte

Koska syöte on niin iso, se annetaan satunnaisgeneraattorin muodossa. Syötteen muodostaa seuraava koodi:

uint64_t next(uint64_t& x) {
	uint64_t z = (x += 0x9e3779b97f4a7c15);
	z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
	z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
	return z ^ (z >> 31);
}

const int N = 1e7;
const int Q = 1e7;
int A[N];
int L[Q];
int R[Q];

void genInput(int n, int q, int h, uint64_t x) {
	for (int i = 0; i < n; ++i) A[i] = next(x) % h;

	for (int i = 0; i < q; ++i) {
		L[i] = next(x) % n;
		R[i] = next(x) % n;
		if (L[i] > R[i]) swap(L[i], R[i]);
	}
}

Ensimmäinen rivi syötettä sisältää neljä lukua n, q, h ja x: taulukon koko, kyselyiden määrä, suurin mahdollinen taulukon arvo ja satunnaisgeneraattorin seedi. Anna nämä arvot genInput-funktiolle.

Kyselyn j, 0 \leq j < q vastaus on pienin arvo A[ i ], kaikkien L[ j ] \leq i \leq R[ j ] yli. Taulukko A on nolla-indeksoitu.

Tuloste

Tulosta yksi luku: kyselyiden vastausten summa.

Rajat

• 1 \leq n \leq 10^7
• 1 \leq q \leq 10^7
• 1 \leq h \leq 10^9

Esimerkki

Syöte:

12 5 10 101

Tuloste:

5

Tällä syötteellä A = [1 1 2 5 9 3 9 7 0 0 3 7], ja kyselyt koskevat intervalleja [1, 7], [4, 10], [3, 10], [1, 5] ja [4, 7]. Vastaukset näihin kyselyihin ovat 1, 0, 0, 1 ja 3.