.wg-container
{
    background: none repeat scroll 0% 0% #2d2d2d;
    border-color: #ddd;
    border-style: solid;
    border-width: 1px 0;
    color: #ccc;
    line-height: 25.6px;
    margin: 0 -20px;
    overflow: auto;
    padding: 15px 20px;
    position: relative;
    text-align: center;
    width: 100%;
    z-index: 0;
}
.wg-container hr
{
    background: #333;
    background-image: -moz-linear-gradient(to right, #333, #ccc, #333);
    background-image: -ms-linear-gradient(to right, #333, #ccc, #333);
    background-image: -o-linear-gradient(to right, #333, #ccc, #333);
    background-image: -webkit-linear-gradient(to right, #333, #ccc, #333);
    border: 0;
    height: 5px;
}
.wg-item
{
    list-style: none;
}
.wg-item .inner
{
    height: 160px;
}
.wg-item li
{
    display: block;
    float: left;
    margin: 16px;
    width: 45%;
}
.wg-item li .header
{
    border: 4px solid #b4b4b4;
    box-shadow: 1px 1px 1px 1px #ccc;
    cursor: pointer;
    float: left;
    height: 256px;
    margin: 5px;
    moz-box-shadow: 1px 1px 1px 1px #ccc;
    overflow: hidden;
    position: relative;
    webkit-box-shadow: 1px 1px 1px 1px #ccc;
    width: 100%;
}
.wg-item li .header:hover a
{
    moz-transform: scale(1.2);
    ms-transform: scale(1.2);
    o-transform: scale(1.2);
    transform: scale(1.2);
    webkit-transform: scale(1.2);
}
.wg-item li .header a
{
    left: 0;
    moz-transition: all 300ms ease-out;
    ms-transition: all 300ms ease-out;
    o-transition: all 300ms ease-out;
    position: absolute;
    transition: all 300ms ease-out;
    webkit-transition: all 300ms ease-out;
}
.wg-item li .image
{
    background-size: cover;
    display: block;
    height: 95%;
    moz-background-size: cover;
    padding: .5em;
    webkit-background-size: cover;
    width: 100%;
}
.wg-item li h3
{
    font-size: 24px;
    font-weight: normal;
    line-height: 22px;
    margin-bottom: 10px;
    margin-top: 10px;
    text-align: center;
}
.wg-item li h3 a:hover
{
    text-decoration: none;
}
.wg-item li ul.links
{
    float: right;
}
.wg-item li .links li
{
    display: block;
    margin-left: 5px;
    margin-right: 0 !important;
    width: initial;
}
.wg-item li .links li a
{
    background: #65a9d7;
    border-radius: 5px;
    box-shadow: 0 1px 0 #000;
    color: #fff;
    font-family: Georgia,Serif;
    font-size: 16px;
    padding: 5.5px 11px;
    text-decoration: none;
    text-shadow: 0 1px 0 rgba(0,0,0,0.4);
    vertical-align: middle;
    webkit-border-radius: 5px;
    webkit-box-shadow: 0 1px 0 #000;
}
.wg-item .description
{
    font-size: 16px;
    margin: .2em 0;
    text-align: left;
}

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
#include <complex>
#include <cmath>
using namespace std;
#define for if (0); else for
using namespace std;
const int MaxFastBits = 16;
int **gFFTBitTable = 0;
int NumberOfBitsNeeded(int PowerOfTwo) {
    for (int i = 0;; ++i) {
        if (PowerOfTwo & (1 << i)) {
            return i;
        }
    }
}
int ReverseBits(int index, int NumBits) {
    int ret = 0;
    for (int i = 0; i < NumBits; ++i, index >>= 1) {
        ret = (ret << 1) | (index & 1);
    }
    return ret;
}
void InitFFT() {
    gFFTBitTable = new int *[MaxFastBits];
    for (int i = 1, length = 2; i <= MaxFastBits; ++i, length <<= 1) {
        gFFTBitTable[i - 1] = new int[length];
        for (int j = 0; j < length; ++j) {
            gFFTBitTable[i - 1][j] = ReverseBits(j, i);
        }
    }
}
inline int FastReverseBits(int i, int NumBits) {
    return NumBits <= MaxFastBits ? gFFTBitTable[NumBits - 1][i] : ReverseBits(i, NumBits);
}
void FFT(bool InverseTransform, vector<complex<double> >& In, vector<complex<double> >& Out) {
    if (!gFFTBitTable) { InitFFT(); }
    // simultaneous data copy and bit-reversal ordering into outputs
    int NumSamples = In.size();
    int NumBits = NumberOfBitsNeeded(NumSamples);
    for (int i = 0; i < NumSamples; ++i) {
        Out[FastReverseBits(i, NumBits)] = In[i];
    }
    // the FFT process
    double angle_numerator = acos(-1.) * (InverseTransform ? -2 : 2);
    for (int BlockEnd = 1, BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1) {
        double delta_angle = angle_numerator / BlockSize;
        double sin1 = sin(-delta_angle);
        double cos1 = cos(-delta_angle);
        double sin2 = sin(-delta_angle * 2);
        double cos2 = cos(-delta_angle * 2);
        for (int i = 0; i < NumSamples; i += BlockSize) {
            complex<double> a1(cos1, sin1), a2(cos2, sin2);
            for (int j = i, n = 0; n < BlockEnd; ++j, ++n) {
                complex<double> a0(2 * cos1 * a1.real() - a2.real(), 2 * cos1 * a1.imag() - a2.imag());
                a2 = a1;
                a1 = a0;
                complex<double> a = a0 * Out[j + BlockEnd];
                Out[j + BlockEnd] = Out[j] - a;
                Out[j] += a;
            }
        }
        BlockEnd = BlockSize;
    }
    // normalize if inverse transform
    if (InverseTransform) {
        for (int i = 0; i < NumSamples; ++i) {
            Out[i] /= NumSamples;
        }
    }
}
vector<double> convolution(vector<double> a, vector<double> b) {
    int n = a.size();
    vector<complex<double> > s(n), d1(n), d2(n), y(n);
    for (int i = 0; i < n; ++i) {
        s[i] = complex<double>(a[i], 0);
    }
    FFT(false, s, d1);
    s[0] = complex<double>(b[0], 0);
    for (int i = 1; i < n; ++i) {
        s[i] = complex<double>(b[n - i], 0);
    }
    FFT(false, s, d2);
    for (int i = 0; i < n; ++i) {
        y[i] = d1[i] * d2[i];
    }
    FFT(true, y, s);
    vector<double> ret(n);
    for (int i = 0; i < n; ++i) {
        ret[i] = s[i].real();
    }
    return ret;
}
struct Polynomial {
    vector<double> v;
    Polynomial operator*(const Polynomial &other) const {
        int n = (int) max(v.size(), other.v.size()) * 2, m;
        for (m = 2; m < n; m <<= 1);
        vector<double> na, nb;
        na.resize(m, 0), nb.resize(m, 0);
        for (int i = 0; i < v.size(); i++)
            na[i] = v[i];
        for (int i = 0, j = m - 1; i < other.v.size(); i++, j--)
            nb[j] = other.v[i];
        Polynomial ret;
        ret.v = convolution(na, nb);
        for (int i = 1; i < ret.v.size(); i++)
            ret.v[i - 1] = ret.v[i];
        ret.v[ret.v.size() - 1] = 0;
        return ret;
    }
};
char sa[1<<18], sb[1<<18];
long long ret[1<<19];
int main() {
    while (scanf("%s %s", sa, sb) == 2) {
        Polynomial a, b, c;
        for (int i = (int)strlen(sa) - 1; i >= 0; i--)
            a.v.push_back(sa[i] - '0');
        
        for (int i = (int)strlen(sb) - 1; i >= 0; i--)
            b.v.push_back(sb[i] - '0');
        c = a * b;
        
        memset(ret, 0, sizeof(ret));
        int f = 0;
        double eps = 1.5e-1;
        for (int i = 0; i < c.v.size(); i++)
            ret[i] = (long long) (c.v[i] + eps);
        int n = (int)c.v.size();
        for (int i = 0; i < n; i++) {
            if (ret[i] >= 10) {
                ret[i + 1] += ret[i]/10;
                ret[i] %= 10;
            }
        }
        for (int i = n; i >= 0; i--) {
            if (ret[i])
                f = 1;
            if (f)
                printf("%lld", ret[i]);
        }
        if (!f)
            printf("0");
        puts("");
    }
    return 0;
}
/*
 0
 5
 
 11
 12
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
#define MAXBUF 8388608
struct Node {
    int lson, rson;
    long long sum;
} node[MAXBUF + 50];
int nodesize = 0;
int root[524288];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int l, int r, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    if (l == r) {
        node[k].sum = val;
        return k;
    }
    int m = (l + r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, l, m, x, val);
    else
        node[k].rson = change(node[p].rson, m+1, r, x, val);
    node[k].sum = node[node[k].lson].sum + node[node[k].rson].sum;
    return k;
}
long long query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return node[k].sum;
    int m = (l + r)/2;
    long long sum = 0;
    if (x <= m) {
        sum += query(node[k].lson, l, m, x, y);
    }
    if (y > m) {
        sum += query(node[k].rson, m+1, r, x, y);
    }
    return sum;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        
        root[0] = build(1, n);
        
        int pre_ver = 0, cmd, x = 0, y = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &cmd, &x);
            if (cmd == 0) {
                y = 0;
                root[i] = root[i - x - 1];
                pre_ver = i;
            } else if (cmd == 1) {
                scanf("%d", &y);
                root[i] = change(root[pre_ver], 1, n, x, y);
                pre_ver = i;
            } else if (cmd == 2){
                scanf("%d", &y);
//                printf("query root = %d\n", root[pre_ver]);
                printf("%lld\n", query(root[pre_ver], 1, n, x, y));
                root[i] = root[pre_ver];
                pre_ver = i;
            }
            if (nodesize > MAXBUF) {
                return 0;
            }
        }
    }
    return 0;
}
/*
 2 5
 1 1 1
 1 2 2
 2 1 2
 0 2
 2 1 2
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[2097152];
int nodesize = 0;
int A[131072], B[131072], root[131072];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
int main() {
    int n, m, x, y, k;
    while (scanf("%d %d", &n, &m) == 2) {
        map<int, int> R;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), R[A[i]] = 0;
        
        int size = 0;
        for (map<int, int>::iterator it = R.begin(); it != R.end(); it++) {
            it->second = ++size;
            B[it->second] = it->first;        
        }
        
        nodesize = 1;
        root[0] = build(1, size);
        
        for (int i = 1; i <= n; i++) {
            A[i] = R[A[i]];
            root[i] = change(root[i-1], A[i], 1);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", B[query(root[y], root[x-1], k)]);
        }
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
double dp[1048576], sum[1048576];
int main() {
    int testcase, cases = 0;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            if (i <= m) {
                dp[i] = 1;
            } else {
                dp[i] = 1 + sum[i - m - 1] * 2.0 / i;
            }
            sum[i] = sum[i - 1] + dp[i];
        }
        printf("Case #%d: %.4lf\n", ++cases, dp[n]);
    }
    return 0;
}
/*
 3
 4 2
 7 2
 10 3
 */

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}
#define INF 0x3f3f3f3f
int main() {
    int testcase, cases = 0;
    int n, s, e;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        vector< pair<int, int> > D;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &s, &e);
            D.push_back(make_pair(s, e));
        }
        sort(D.begin(), D.end(), cmp);
        vector<int> leftside;
        for (int i = 0; i < D.size(); i++) {
            int pos = (int)(lower_bound(leftside.begin(), leftside.end(), D[i].first + 1)
                            - leftside.begin());
            if (pos == leftside.size()) {
                leftside.push_back(D[i].first);
            } else {
                leftside[pos] = D[i].first;
            }
        }
        printf("Case %d: %d\n", ++cases, (int)leftside.size());
    }
    return 0;
}

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
struct Edge {
    int to, w, i;
    Edge(int a = 0, int b = 0, int c = 0):
        to(a), w(b), i(c) {}
};
vector<Edge> g[16];
int n, used[1<<16];
double dp[1<<16];
double dfs(int);
void dfs2(int u, int mask, int w, int e, int o) {
    if (e) {
        dp[o] = min(dp[o], dfs(mask) + (double)w/e);
    }
    for (int i = 0; i < g[u].size(); i++) {
        if ((mask>>g[u][i].i)&1) {
            int v = g[u][i].to;
            dfs2(v, mask^(1<<g[u][i].i), w + g[u][i].w, e+1, o);
        }
    }
}
double dfs(int mask) {
    if (mask == 0)  return 0;
    if (used[mask]) return dp[mask];
    used[mask] = 1;
    double &ret = dp[mask];
    ret = 1e+30;
    for (int i = 0; i < n; i++) {
        dfs2(i, mask, 0, 0, mask);
    }
    return ret;
}
int main() {
    int x, y, w;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(Edge(y, w, i));
            g[y].push_back(Edge(x, w, i));
        }
        memset(used, 0, sizeof(used));
        printf("%.4lf\n", dfs((1<<(n-1)) - 1));
    }
    return 0;
}
/*
 4
 0 2 1
 1 2 2
 2 3 3
 6
 0 1 10000
 0 2 10000
 0 3 1
 0 4 1
 0 5 10000
 0 */

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
int n;
int h[1048576], a[1048576];
int main() {
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &h[i]), a[i] = h[i];
        
        stack< pair<int, int> > stk;
        for (int i = 0; i < n; i++) {
            if (!stk.empty()) {
                stk.top().second = min(stk.top().second, h[i]);
            }
            while (!stk.empty() && stk.top().first <= h[i]) {
                pair<int, int> p = stk.top();
                stk.pop();
                if (!stk.empty())
                    stk.top().second = min(stk.top().second, p.second);
            }
            if (!stk.empty()) {
                a[i] = min(a[i], h[i] - stk.top().second);
            }
            stk.push(make_pair(h[i], h[i]));
        }
        
        while (!stk.empty())
            stk.pop();
            
        for (int i = n - 1; i >= 0; i--) {
            if (!stk.empty()) {
                stk.top().second = min(stk.top().second, h[i]);
            }
            while (!stk.empty() && stk.top().first <= h[i]) {
                pair<int, int> p = stk.top();
                stk.pop();
                if (!stk.empty())
                    stk.top().second = min(stk.top().second, p.second);
            }
            if (!stk.empty()) {
                a[i] = min(a[i], h[i] - stk.top().second);
            }
            stk.push(make_pair(h[i], h[i]));
        }
        
        int f = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] >= 150000) {
                if (f++) printf(" ");
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 5
 0 10000 100000 884813 0
 7
 0 100000 0 200000 180000 200000 0
 */