O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune 1 × N, fiind apoi împărțit în parcele de dimensiune 1 x 1. Pe fiecare dintre cele N parcele de dimensiune 1 × 1 firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la 1 la N, altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu h1, h2, …, hN altitudinile parcelelor, există un indice vf, 1 ≤ vf ≤ N, astfel încât h1 < h2 <... < hvf-1 < hvf > hvf+1 > ... > hN.

Exemplu

colina.in

6 5
1 5 9 7 2 1
5 6 1 9 4

colina.out

DA 2
NU
DA 1 6
DA 3
NU

#include <bits/stdc++.h>

using namespace std;

ifstream cin("colina.in");
ofstream cout("colina.out");

int n, m;

struct bla{
    int val, poz;
}a[100001];

bool comp(bla a, bla b){
    if(a.val != b.val)
        return a.val < b.val;
    return a.poz < b.poz;
}

void CB(int x){
    int st = 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij].val > x)
            dr = mij-1;
        else if(a[mij].val < x)
            st = mij+1;
        else{
            int i = mij;
            while(a[i].val == x)
                i--;
            i++;
            cout << "DA ";
            while(a[i].val == x)
                cout << a[i].poz << ' ', i++;
            cout << "\n";
            return;
        }
    }
    cout << "NU" << "\n";
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i].val, a[i].poz = i;
    sort(a + 1, a + n + 1, comp);
    int x;
    for(int i = 1; i <= m; ++i){
        cin >> x;
        CB(x);
    }
    return 0;
}