#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <iterator>
#include <map>
#include <cstring>
#include <climits>
#include <time.h>
using namespace std;
#define READ() freopen("in.txt","r",stdin)
#define WRITE() freopen("out.txt","w",stdout)
#define sf(n) scanf("%d",&n)
#define lsf(n) scanf("%lld", &n)
#define pb(n) push_back(n)
#define EPS 1e-10
#define NL printf("\n")
#define INF INT_MAX
#define MAX 500010
#define MOD 1000000007
#define LL long long
#define callLeft()
#define callRight() (right,mid+1,j)
#define cnd tree[idx]
#define lnd tree[left]
#define rnd tree[left+1]
using namespace std;
/**
problem: how many numbers in a segment that appears exactly 2 times!
PREREQUSITE : loj - 1188; i wrote an editorial there.
Solution : off-line solve, segment tree.
okay lets jump into it with an example (given array):
8
1 1 1 2 3 5 1 2
first lets solve the problem if the query always starts from 0th index and ends at any index.
how to approach that?
using this array: 0 1 -1 0 0 0 0 1 (and make cumulative sum array of course!)
query [0-7] ans = 1. correct.
query [0-1] ans = 1. correct.
okay let me explain how i made this array here.
we marked the index where x has appeared 2nd time as 1, meaning:
till this index, there is an answer.
then, as we need numbers who are present EXACTLY 2 times,
we marked the the index where x has appeared 3rd time as -1, which
crosses out index where x appeared 2nd time, meaning:
till this point there is no answer! i hope the making of the array is clear now!
now the next part,
what happens when the starting index of query is not 0th index?
this is where off-line solve comes into play!
we will use this array still:
0 1 -1 0 0 0 0 1
but how do we get the answer when the query is lets say [1,2]
using current array if we try to find the answer then the answer will be 0, which is wrong!
so how do we find it? think about it!
if we make the 1st index 0, 2nd index 1 and 6th index -1 then
we can answer any query starting from 1st index! :D
and the array is : 0 0 1 0 0 0 -1 1
can you say why we specifically updated the 1st,2nd,6th index?
because those are the places where 1 is present.
and we changed the positions where 1 is present, why?
because 1 is 0th index, which is the previous 1st index.
so for example if the query is [2-7]
the we would have to do the same for 0th index value, 1st index value.
and the array will be like:
0 0 0 0 0 0 1 1
and the answer is 2!
we simple used segment tree to update and find the query.
**/
struct Qinfo /// query input goes here
{
int x,y,i;
};
bool QinfoCmp(Qinfo x1, Qinfo x2) /// sort by x
{
if(x1.x < x2.x)return true;
else if(x1.x == x2.x)
{
if(x1.y < x2.y)return true;
return false;
}
return false;
}
int prevUsed[MAX]; /// to remember if it was used before!
int treeBuild[MAX]; /// to initialize the values and build tree
///**********************************************************Segment Tree Starts*****************************
/// Segment Tree Type: Simple summation in range
struct node
{
int sum;
node()
{
sum = 0;
}
};
node tree[4*MAX];
void mergeNodes(int idx,int left,int right)
{
cnd.sum = (tree[left].sum + tree[right].sum);
}
void build(int idx,int st,int ed)
{
if(st == ed)
{
cnd.sum = treeBuild[st];
return;
}
int left = idx*2;
int right = left+1;
int mid = (st+ed)/2;
build(left,st,mid);
build(right,mid+1,ed);
mergeNodes(idx,left,right);
}
void update(int idx,int st,int ed,int i,int j,int v)
{
if(i > ed || j < st)return;
if(st >= i && ed <= j)
{
cnd.sum = v;
return;
}
int left = idx<<1;
int right = left+1;
int mid = (st+ed)>>1;
update(left,st,mid,i,j,v);
update(right,mid+1,ed,i,j,v);
mergeNodes(idx,left,right);
}
int query(int idx,int st,int ed,int i,int j)
{
if(i > ed || j < st)return 0;
if(st >= i && ed <= j)
{
return cnd.sum;
}
int left = idx<<1;
int right = left+1;
int mid = (st+ed)>>1;
return (query(left,st,mid,i,j) + query(right,mid+1,ed,i,j));
}
///**********************************************************Segment Tree Ends*****************************
int arr[MAX]; /// input arr
vector <int> vec[MAX]; /// used for next index of value X
int lastIndex[MAX]; /// keeping count of how many indexed used of value X
Qinfo qi[MAX]; /// storing query
int ansStore[MAX]; /// storing answer
int main()
{
// READ();
// WRITE();
int t;
// sf(t);
t = 1;
int TC = 0;
while(t--)
{
int n;
sf(n);
int q;
sf(q);
// memset(arr,0,sizeof(arr));
memset(tree,0,sizeof(tree));
memset(prevUsed,false,sizeof(prevUsed));
memset(lastIndex,0,sizeof(lastIndex));
memset(treeBuild,false,sizeof(treeBuild));
// memset(xStore,-1,sizeof(xStore));
for(int i=0;i<MAX;i++)vec[i].clear();
map <int,int> mp;
int cntDistVal = 1;
for(int i=1;i<=n;i++)
{
sf(arr[i]);
if(mp.find(arr[i]) == mp.end())mp[arr[i]] = cntDistVal++;
}
for(int i=1;i<=n;i++)
{
int x = mp[arr[i]];
if(prevUsed[x] == 0)
{
prevUsed[x]++;
treeBuild[i] = 0;
}
else if(prevUsed[x] == 1)
{
prevUsed[x]++;
treeBuild[i] = 1;
}
else if(prevUsed[x] == 2)
{
prevUsed[x]++;
treeBuild[i] = -1;
}
else treeBuild[i] = 0;
vec[x].pb(i);
}
// n = cntDistVal;
build(1,1,n);
for(int i=0;i<q;i++)
{
int x,y;
sf(x);
sf(y);
qi[i].x = x;
qi[i].y = y;
qi[i].i = i;
}
sort(qi,qi+q,QinfoCmp);
// for(int i=0;i<q;i++)
// {
// cout << qi[i].x << " to " << qi[i].y << " index:" << qi[i].i << endl;
// }
int initStart = 1;
for(int i=0;i<q;i++)
{
// cout << qi[i].x << " to " << qi[i].y << " index:" << qi[i].i << endl;
int qX = qi[i].x;
while(initStart != qX) /// sweeping from left to right
{
// int vecI = arr[initStart];
int vecI = mp[arr[initStart]];
int updateIndex = vec[vecI][lastIndex[vecI]];
// cout << "update 0 at: " << updateIndex << endl;
update(1,1,n,updateIndex,updateIndex,0); /// making current index 0
if(vec[vecI].size() > lastIndex[vecI] + 1)
{
// lastIndex[vecI]++;
updateIndex = vec[vecI][lastIndex[vecI]+1]; /// making next index 0
// cout << "update 1 at: " << updateIndex << endl;
update(1,1,n,updateIndex,updateIndex,0);
}
if(vec[vecI].size() > lastIndex[vecI] + 2)
{
// lastIndex[vecI]+=2;
updateIndex = vec[vecI][lastIndex[vecI]+2]; /// making next index 1
// cout << "update 1 at: " << updateIndex << endl;
update(1,1,n,updateIndex,updateIndex,1);
}
if(vec[vecI].size() > lastIndex[vecI] + 3)
{
// lastIndex[vecI]+=2;
updateIndex = vec[vecI][lastIndex[vecI]+3]; /// making next index -1
// cout << "update 1 at: " << updateIndex << endl;
update(1,1,n,updateIndex,updateIndex,-1);
}
lastIndex[vecI]++;
initStart++;
}
int qrr = query(1,1,n,qi[i].x,qi[i].y); /// query
ansStore[qi[i].i] = qrr; /// saving
// cout << "ans : " << qrr << endl;
// cout << endl << endl;
}
// printf("Case %d:\n",++TC);
for(int i=0;i<q;i++)
{
printf("%d\n",ansStore[i]);
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDx0aW1lLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBSRUFEKCkgCWZyZW9wZW4oImluLnR4dCIsInIiLHN0ZGluKQojZGVmaW5lIFdSSVRFKCkgZnJlb3Blbigib3V0LnR4dCIsInciLHN0ZG91dCkKI2RlZmluZSBzZihuKSAJc2NhbmYoIiVkIiwmbikKI2RlZmluZSBsc2YobikgCXNjYW5mKCIlbGxkIiwgJm4pCiNkZWZpbmUgcGIobikgCXB1c2hfYmFjayhuKQojZGVmaW5lIEVQUyAJMWUtMTAKI2RlZmluZSBOTCAJCXByaW50ZigiXG4iKQojZGVmaW5lIElORiAgICAgSU5UX01BWAojZGVmaW5lIE1BWCAgICAgNTAwMDEwCiNkZWZpbmUgTU9EICAgICAxMDAwMDAwMDA3CiNkZWZpbmUgTEwgICAgICBsb25nIGxvbmcKCiNkZWZpbmUgY2FsbExlZnQoKQojZGVmaW5lIGNhbGxSaWdodCgpIChyaWdodCxtaWQrMSxqKQojZGVmaW5lIGNuZCB0cmVlW2lkeF0KI2RlZmluZSBsbmQgdHJlZVtsZWZ0XQojZGVmaW5lIHJuZCB0cmVlW2xlZnQrMV0KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovKioKcHJvYmxlbTogaG93IG1hbnkgbnVtYmVycyBpbiBhIHNlZ21lbnQgdGhhdCBhcHBlYXJzIGV4YWN0bHkgMiB0aW1lcyEKUFJFUkVRVVNJVEUgOiBsb2ogLSAxMTg4OyBpIHdyb3RlIGFuIGVkaXRvcmlhbCB0aGVyZS4KU29sdXRpb24gOiBvZmYtbGluZSBzb2x2ZSwgc2VnbWVudCB0cmVlLgpva2F5IGxldHMganVtcCBpbnRvIGl0IHdpdGggYW4gZXhhbXBsZSAoZ2l2ZW4gYXJyYXkpOgo4CjEgMSAxIDIgMyA1IDEgMgoKZmlyc3QgbGV0cyBzb2x2ZSB0aGUgcHJvYmxlbSBpZiB0aGUgcXVlcnkgYWx3YXlzIHN0YXJ0cyBmcm9tIDB0aCBpbmRleCBhbmQgZW5kcyBhdCBhbnkgaW5kZXguCmhvdyB0byBhcHByb2FjaCB0aGF0Pwp1c2luZyB0aGlzIGFycmF5OiAwIDEgLTEgMCAwIDAgMCAxIChhbmQgbWFrZSBjdW11bGF0aXZlIHN1bSBhcnJheSBvZiBjb3Vyc2UhKQpxdWVyeSBbMC03XSBhbnMgPSAxLiBjb3JyZWN0LgpxdWVyeSBbMC0xXSBhbnMgPSAxLiBjb3JyZWN0Lgpva2F5IGxldCBtZSBleHBsYWluIGhvdyBpIG1hZGUgdGhpcyBhcnJheSBoZXJlLgp3ZSBtYXJrZWQgdGhlIGluZGV4IHdoZXJlIHggaGFzIGFwcGVhcmVkIDJuZCB0aW1lIGFzIDEsIG1lYW5pbmc6CnRpbGwgdGhpcyBpbmRleCwgdGhlcmUgaXMgYW4gYW5zd2VyLgoKdGhlbiwgYXMgd2UgbmVlZCBudW1iZXJzIHdobyBhcmUgcHJlc2VudCBFWEFDVExZIDIgdGltZXMsCndlIG1hcmtlZCB0aGUgdGhlIGluZGV4IHdoZXJlIHggaGFzIGFwcGVhcmVkIDNyZCB0aW1lIGFzIC0xLCB3aGljaApjcm9zc2VzIG91dCBpbmRleCB3aGVyZSB4IGFwcGVhcmVkIDJuZCB0aW1lLCBtZWFuaW5nOgp0aWxsIHRoaXMgcG9pbnQgdGhlcmUgaXMgbm8gYW5zd2VyISBpIGhvcGUgdGhlIG1ha2luZyBvZiB0aGUgYXJyYXkgaXMgY2xlYXIgbm93IQoKbm93IHRoZSBuZXh0IHBhcnQsCndoYXQgaGFwcGVucyB3aGVuIHRoZSBzdGFydGluZyBpbmRleCBvZiBxdWVyeSBpcyBub3QgMHRoIGluZGV4Pwp0aGlzIGlzIHdoZXJlIG9mZi1saW5lIHNvbHZlIGNvbWVzIGludG8gcGxheSEKCndlIHdpbGwgdXNlIHRoaXMgYXJyYXkgc3RpbGw6CjAgMSAtMSAwIDAgMCAwIDEKCmJ1dCBob3cgZG8gd2UgZ2V0IHRoZSBhbnN3ZXIgd2hlbiB0aGUgcXVlcnkgaXMgbGV0cyBzYXkgWzEsMl0KdXNpbmcgY3VycmVudCBhcnJheSBpZiB3ZSB0cnkgdG8gZmluZCB0aGUgYW5zd2VyIHRoZW4gdGhlIGFuc3dlciB3aWxsIGJlIDAsIHdoaWNoIGlzIHdyb25nIQpzbyBob3cgZG8gd2UgZmluZCBpdD8gdGhpbmsgYWJvdXQgaXQhCmlmIHdlIG1ha2UgdGhlIDFzdCBpbmRleCAwLCAybmQgaW5kZXggMSBhbmQgNnRoIGluZGV4IC0xIHRoZW4Kd2UgY2FuIGFuc3dlciBhbnkgcXVlcnkgc3RhcnRpbmcgZnJvbSAxc3QgaW5kZXghIDpECmFuZCB0aGUgYXJyYXkgaXMgOiAwIDAgMSAwIDAgMCAtMSAxCgpjYW4geW91IHNheSB3aHkgd2Ugc3BlY2lmaWNhbGx5IHVwZGF0ZWQgdGhlIDFzdCwybmQsNnRoIGluZGV4PwpiZWNhdXNlIHRob3NlIGFyZSB0aGUgcGxhY2VzIHdoZXJlIDEgaXMgcHJlc2VudC4KYW5kIHdlIGNoYW5nZWQgdGhlIHBvc2l0aW9ucyB3aGVyZSAxIGlzIHByZXNlbnQsIHdoeT8KYmVjYXVzZSAxIGlzIDB0aCBpbmRleCwgd2hpY2ggaXMgdGhlIHByZXZpb3VzIDFzdCBpbmRleC4KCnNvIGZvciBleGFtcGxlIGlmIHRoZSBxdWVyeSBpcyBbMi03XQp0aGUgd2Ugd291bGQgaGF2ZSB0byBkbyB0aGUgc2FtZSBmb3IgMHRoIGluZGV4IHZhbHVlLCAxc3QgaW5kZXggdmFsdWUuCmFuZCB0aGUgYXJyYXkgd2lsbCBiZSBsaWtlOgowIDAgMCAwIDAgMCAxIDEKYW5kIHRoZSBhbnN3ZXIgaXMgMiEKCndlIHNpbXBsZSB1c2VkIHNlZ21lbnQgdHJlZSB0byB1cGRhdGUgYW5kIGZpbmQgdGhlIHF1ZXJ5LgoqKi8KCnN0cnVjdCBRaW5mbyAvLy8gcXVlcnkgaW5wdXQgZ29lcyBoZXJlCnsKICAgIGludCB4LHksaTsKfTsKCmJvb2wgUWluZm9DbXAoUWluZm8geDEsIFFpbmZvIHgyKSAvLy8gc29ydCBieSB4CnsKICAgIGlmKHgxLnggPCB4Mi54KXJldHVybiB0cnVlOwogICAgZWxzZSBpZih4MS54ID09IHgyLngpCiAgICB7CiAgICAgICAgaWYoeDEueSA8IHgyLnkpcmV0dXJuIHRydWU7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogICAgIHJldHVybiBmYWxzZTsKfQppbnQgcHJldlVzZWRbTUFYXTsgLy8vIHRvIHJlbWVtYmVyIGlmIGl0IHdhcyB1c2VkIGJlZm9yZSEKaW50IHRyZWVCdWlsZFtNQVhdOyAvLy8gdG8gaW5pdGlhbGl6ZSB0aGUgdmFsdWVzIGFuZCBidWlsZCB0cmVlCgovLy8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqU2VnbWVudCBUcmVlIFN0YXJ0cyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqCi8vLyBTZWdtZW50IFRyZWUgVHlwZTogU2ltcGxlIHN1bW1hdGlvbiBpbiByYW5nZQpzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgc3VtOwogICAgbm9kZSgpCiAgICB7CiAgICAgICAgc3VtID0gMDsKICAgIH0KfTsKCm5vZGUgdHJlZVs0Kk1BWF07Cgp2b2lkIG1lcmdlTm9kZXMoaW50IGlkeCxpbnQgbGVmdCxpbnQgcmlnaHQpCnsKICAgIGNuZC5zdW0gPSAodHJlZVtsZWZ0XS5zdW0gKyB0cmVlW3JpZ2h0XS5zdW0pOwp9Cgp2b2lkIGJ1aWxkKGludCBpZHgsaW50IHN0LGludCBlZCkKewogICAgaWYoc3QgPT0gZWQpCiAgICB7CiAgICAgICAgY25kLnN1bSA9IHRyZWVCdWlsZFtzdF07CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IGxlZnQgPSBpZHgqMjsKICAgIGludCByaWdodCA9IGxlZnQrMTsKICAgIGludCBtaWQgPSAoc3QrZWQpLzI7CgogICAgYnVpbGQobGVmdCxzdCxtaWQpOwogICAgYnVpbGQocmlnaHQsbWlkKzEsZWQpOwogICAgbWVyZ2VOb2RlcyhpZHgsbGVmdCxyaWdodCk7Cn0KCnZvaWQgdXBkYXRlKGludCBpZHgsaW50IHN0LGludCBlZCxpbnQgaSxpbnQgaixpbnQgdikKewogICAgaWYoaSA+IGVkIHx8IGogPCBzdClyZXR1cm47CiAgICBpZihzdCA+PSBpICYmIGVkIDw9IGopCiAgICB7CiAgICAgICAgY25kLnN1bSA9IHY7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IGxlZnQgPSBpZHg8PDE7CiAgICBpbnQgcmlnaHQgPSBsZWZ0KzE7CiAgICBpbnQgbWlkID0gKHN0K2VkKT4+MTsKCiAgICB1cGRhdGUobGVmdCxzdCxtaWQsaSxqLHYpOwogICAgdXBkYXRlKHJpZ2h0LG1pZCsxLGVkLGksaix2KTsKCiAgICBtZXJnZU5vZGVzKGlkeCxsZWZ0LHJpZ2h0KTsKfQoKaW50IHF1ZXJ5KGludCBpZHgsaW50IHN0LGludCBlZCxpbnQgaSxpbnQgaikKewogICAgaWYoaSA+IGVkIHx8IGogPCBzdClyZXR1cm4gMDsKICAgIGlmKHN0ID49IGkgJiYgZWQgPD0gaikKICAgIHsKICAgICAgICByZXR1cm4gY25kLnN1bTsKICAgIH0KCiAgICBpbnQgbGVmdCA9IGlkeDw8MTsKICAgIGludCByaWdodCA9IGxlZnQrMTsKICAgIGludCBtaWQgPSAoc3QrZWQpPj4xOwoKICAgIHJldHVybiAocXVlcnkobGVmdCxzdCxtaWQsaSxqKSArIHF1ZXJ5KHJpZ2h0LG1pZCsxLGVkLGksaikpOwp9Ci8vLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKipTZWdtZW50IFRyZWUgRW5kcyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqCgoKaW50IGFycltNQVhdOyAvLy8gaW5wdXQgYXJyCnZlY3RvciA8aW50PiB2ZWNbTUFYXTsgLy8vIHVzZWQgZm9yIG5leHQgaW5kZXggb2YgdmFsdWUgWAppbnQgbGFzdEluZGV4W01BWF07IC8vLyBrZWVwaW5nIGNvdW50IG9mIGhvdyBtYW55IGluZGV4ZWQgdXNlZCBvZiB2YWx1ZSBYClFpbmZvIHFpW01BWF07IC8vLyBzdG9yaW5nIHF1ZXJ5CmludCBhbnNTdG9yZVtNQVhdOyAvLy8gc3RvcmluZyBhbnN3ZXIKCmludCBtYWluKCkKewovLyAgICBSRUFEKCk7Ci8vICAgIFdSSVRFKCk7CgogICAgaW50IHQ7Ci8vICAgIHNmKHQpOwogICAgdCA9IDE7CiAgICBpbnQgVEMgPSAwOwoKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBpbnQgbjsKICAgICAgICBzZihuKTsKICAgICAgICBpbnQgcTsKICAgICAgICBzZihxKTsKLy8gICAgICAgIG1lbXNldChhcnIsMCxzaXplb2YoYXJyKSk7CiAgICAgICAgbWVtc2V0KHRyZWUsMCxzaXplb2YodHJlZSkpOwogICAgICAgIG1lbXNldChwcmV2VXNlZCxmYWxzZSxzaXplb2YocHJldlVzZWQpKTsKICAgICAgICBtZW1zZXQobGFzdEluZGV4LDAsc2l6ZW9mKGxhc3RJbmRleCkpOwogICAgICAgIG1lbXNldCh0cmVlQnVpbGQsZmFsc2Usc2l6ZW9mKHRyZWVCdWlsZCkpOwovLyAgICAgICAgbWVtc2V0KHhTdG9yZSwtMSxzaXplb2YoeFN0b3JlKSk7CgogICAgICAgIGZvcihpbnQgaT0wO2k8TUFYO2krKyl2ZWNbaV0uY2xlYXIoKTsKCiAgICAgICAgbWFwIDxpbnQsaW50PiBtcDsKICAgICAgICBpbnQgY250RGlzdFZhbCA9IDE7CiAgICAgICAgZm9yKGludCBpPTE7aTw9bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBzZihhcnJbaV0pOwogICAgICAgICAgICBpZihtcC5maW5kKGFycltpXSkgPT0gbXAuZW5kKCkpbXBbYXJyW2ldXSA9IGNudERpc3RWYWwrKzsKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpPTE7aTw9bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgeCA9IG1wW2FycltpXV07CgogICAgICAgICAgICBpZihwcmV2VXNlZFt4XSA9PSAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwcmV2VXNlZFt4XSsrOwogICAgICAgICAgICAgICAgdHJlZUJ1aWxkW2ldID0gMDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmKHByZXZVc2VkW3hdID09IDEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHByZXZVc2VkW3hdKys7CiAgICAgICAgICAgICAgICB0cmVlQnVpbGRbaV0gPSAxOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocHJldlVzZWRbeF0gPT0gMikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcHJldlVzZWRbeF0rKzsKICAgICAgICAgICAgICAgIHRyZWVCdWlsZFtpXSA9IC0xOwogICAgICAgICAgICB9CgogICAgICAgICAgICBlbHNlIHRyZWVCdWlsZFtpXSA9IDA7CgogICAgICAgICAgICB2ZWNbeF0ucGIoaSk7CiAgICAgICAgfQovLyAgICAgICAgbiA9IGNudERpc3RWYWw7CiAgICAgICAgYnVpbGQoMSwxLG4pOwoKICAgICAgICBmb3IoaW50IGk9MDtpPHE7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHgseTsKICAgICAgICAgICAgc2YoeCk7CiAgICAgICAgICAgIHNmKHkpOwogICAgICAgICAgICBxaVtpXS54ID0geDsKICAgICAgICAgICAgcWlbaV0ueSA9IHk7CiAgICAgICAgICAgIHFpW2ldLmkgPSBpOwogICAgICAgIH0KICAgICAgICBzb3J0KHFpLHFpK3EsUWluZm9DbXApOwoKLy8gICAgICAgIGZvcihpbnQgaT0wO2k8cTtpKyspCi8vICAgICAgICB7Ci8vICAgICAgICAgICAgY291dCA8PCBxaVtpXS54IDw8ICIgdG8gIiA8PCBxaVtpXS55IDw8ICIgIGluZGV4OiIgPDwgcWlbaV0uaSA8PCBlbmRsOwovLyAgICAgICAgfQoKICAgICAgICBpbnQgaW5pdFN0YXJ0ID0gMTsKICAgICAgICBmb3IoaW50IGk9MDtpPHE7aSsrKQogICAgICAgIHsKLy8gICAgICAgICAgICBjb3V0IDw8IHFpW2ldLnggPDwgIiB0byAiIDw8IHFpW2ldLnkgPDwgIiAgaW5kZXg6IiA8PCBxaVtpXS5pIDw8IGVuZGw7CiAgICAgICAgICAgIGludCBxWCA9IHFpW2ldLng7CiAgICAgICAgICAgIHdoaWxlKGluaXRTdGFydCAhPSBxWCkgLy8vIHN3ZWVwaW5nIGZyb20gbGVmdCB0byByaWdodAogICAgICAgICAgICB7Ci8vICAgICAgICAgICAgICAgIGludCB2ZWNJID0gYXJyW2luaXRTdGFydF07CiAgICAgICAgICAgICAgICBpbnQgdmVjSSA9IG1wW2Fycltpbml0U3RhcnRdXTsKICAgICAgICAgICAgICAgIGludCB1cGRhdGVJbmRleCA9IHZlY1t2ZWNJXVtsYXN0SW5kZXhbdmVjSV1dOwovLyAgICAgICAgICAgICAgICBjb3V0IDw8ICJ1cGRhdGUgMCBhdDogIiA8PCB1cGRhdGVJbmRleCA8PCBlbmRsOwogICAgICAgICAgICAgICAgdXBkYXRlKDEsMSxuLHVwZGF0ZUluZGV4LHVwZGF0ZUluZGV4LDApOyAvLy8gbWFraW5nIGN1cnJlbnQgaW5kZXggMAoKICAgICAgICAgICAgICAgIGlmKHZlY1t2ZWNJXS5zaXplKCkgPiBsYXN0SW5kZXhbdmVjSV0gKyAxKQogICAgICAgICAgICAgICAgewovLyAgICAgICAgICAgICAgICAgICAgbGFzdEluZGV4W3ZlY0ldKys7CiAgICAgICAgICAgICAgICAgICAgdXBkYXRlSW5kZXggPSB2ZWNbdmVjSV1bbGFzdEluZGV4W3ZlY0ldKzFdOyAvLy8gbWFraW5nIG5leHQgaW5kZXggMAovLyAgICAgICAgICAgICAgICAgICAgY291dCA8PCAidXBkYXRlIDEgYXQ6ICIgPDwgdXBkYXRlSW5kZXggPDwgZW5kbDsKICAgICAgICAgICAgICAgICAgICB1cGRhdGUoMSwxLG4sdXBkYXRlSW5kZXgsdXBkYXRlSW5kZXgsMCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZih2ZWNbdmVjSV0uc2l6ZSgpID4gbGFzdEluZGV4W3ZlY0ldICsgMikKICAgICAgICAgICAgICAgIHsKLy8gICAgICAgICAgICAgICAgICAgIGxhc3RJbmRleFt2ZWNJXSs9MjsKICAgICAgICAgICAgICAgICAgICB1cGRhdGVJbmRleCA9IHZlY1t2ZWNJXVtsYXN0SW5kZXhbdmVjSV0rMl07IC8vLyBtYWtpbmcgbmV4dCBpbmRleCAxCi8vICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICJ1cGRhdGUgMSBhdDogIiA8PCB1cGRhdGVJbmRleCA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgIHVwZGF0ZSgxLDEsbix1cGRhdGVJbmRleCx1cGRhdGVJbmRleCwxKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmKHZlY1t2ZWNJXS5zaXplKCkgPiBsYXN0SW5kZXhbdmVjSV0gKyAzKQogICAgICAgICAgICAgICAgewovLyAgICAgICAgICAgICAgICAgICAgbGFzdEluZGV4W3ZlY0ldKz0yOwogICAgICAgICAgICAgICAgICAgIHVwZGF0ZUluZGV4ID0gdmVjW3ZlY0ldW2xhc3RJbmRleFt2ZWNJXSszXTsgLy8vIG1ha2luZyBuZXh0IGluZGV4IC0xCi8vICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICJ1cGRhdGUgMSBhdDogIiA8PCB1cGRhdGVJbmRleCA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgIHVwZGF0ZSgxLDEsbix1cGRhdGVJbmRleCx1cGRhdGVJbmRleCwtMSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBsYXN0SW5kZXhbdmVjSV0rKzsKCiAgICAgICAgICAgICAgICBpbml0U3RhcnQrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgcXJyID0gcXVlcnkoMSwxLG4scWlbaV0ueCxxaVtpXS55KTsgLy8vIHF1ZXJ5CiAgICAgICAgICAgIGFuc1N0b3JlW3FpW2ldLmldID0gcXJyOyAvLy8gc2F2aW5nCi8vICAgICAgICAgICAgY291dCA8PCAiYW5zIDogIiA8PCBxcnIgPDwgZW5kbDsKLy8gICAgICAgICAgICBjb3V0IDw8IGVuZGwgPDwgZW5kbDsKICAgICAgICB9CgovLyAgICAgICAgcHJpbnRmKCJDYXNlICVkOlxuIiwrK1RDKTsKICAgICAgICBmb3IoaW50IGk9MDtpPHE7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixhbnNTdG9yZVtpXSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0KCgoK